March 2, 2006 at 1:51 pm
I have read that indexes are stored in a B-Tree format and that B-Trees are balanced. Can someone please explain the balanced bit because I don't understand the significance of the statement? The paragraph I read mentions "any search of the index requires that SQL Server navigate the same number of levels and pages in the index to retrieve the data"?!
March 2, 2006 at 3:55 pm
A btree is a series of nodes with two branches eg:
10
|
---------
| |
5 20
A balanced btree basically has a structure that is not overbalanced on the left or right
Above is balanced
Below is unbalanced on the left.
10
|
-----
9 11
|
--
8
|
--
|
7
The above could be balanced by making 9 the root node
9
|
-----
| |
8 10
| |
-- --
| |
7 11
Hope that helps.
March 3, 2006 at 1:33 am
Hi Keith,
So assume I had a Root level with two intermediate levels each having three leaf level nodes in my clustered index. If I delete a load of rows that happen to be on only one side of my tree causing one of the leaf level nodes to contain no data, SQL Server will then recalculate the entire data set and split the data pages so that the same amount of data is on both sides of the tree. Is that right?
Thanks
David
March 3, 2006 at 8:26 am
Check out http://en.wikipedia.org/wiki/B_tree
and http://en.wikipedia.org/wiki/Category:Trees_%28structure%29
There is some fascinating stuff on how trees can be designed and how rebalancing works.
jg
March 7, 2006 at 12:58 am
Thank you both for your contributions, I think I have a better understanding now!
May 28, 2006 at 10:11 am
hi all, im new on this site and i was wondering whether any 1 could tell me the advantages of b trees in a physical database?
thanks
Viewing 6 posts - 1 through 6 (of 6 total)
You must be logged in to reply to this topic. Login to reply