The scenario: When a user updates some information - the correct row must be found and updated.

I'm debating between two options:

  1. Let the server search through all of the rows (-slow). But be fast on the update.
  2. Index, and therefore be fast to find, but slow to update.

It seems that if the index is a binary tree - updating will be quick and therefore indexing is better. And if not - not-indexing would be better because indexing will lose more when updating than gain when searching.

(Note that every user-action here will have both a search and an update.)

More info:

  • I'm referring mainly to non-clustered indexing.
  • Currently there are very few rows so it's difficult to assess the speed if and when there will be over 1-10 million rows.
  • Shouldn't be difficult to assess the speed. You have some idea of what your data looks like, right? So generate a lot of it on a test system. – Aaron Bertrand Mar 10 '14 at 19:55
  • @AaronBertrand Thanks. That sounds like sound advice. (Though, I'd still be interested in the answer to my question.) – ispiro Mar 10 '14 at 19:57
  • I'd still be interested in what your actual question is. :-) – Aaron Bertrand Mar 10 '14 at 19:58
  • 1
    And the index is not a binary tree, but a balanced tree. One of many explanations: use-the-index-luke.com/sql/anatomy/the-tree – RLF Mar 10 '14 at 19:58
  • 2
    SQL Server indexing uses a B-tree, not a binary tree. In general, indexes speed up searches and sorts and joins and slow down modifications. How much indexing you need depends on your application. – Greenstone Walker Mar 10 '14 at 20:03

SQL Server B-Tree indexes are not binary trees, but balanced trees. This structure allows a tree traversal which is much more shallow, and therefore likely results in a more rapid index search. This also affects the scope of updates to the indexes.

See one explanation at: http://use-the-index-luke.com/sql/anatomy/the-tree

| improve this answer | |
  • Even if DBMS were using binary trees, we'd still have logarithimic gain. – ypercubeᵀᴹ Mar 11 '14 at 0:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.