November 7, 2009 at 12:26 pm
Hi,
I have 10,000 records in a table.
What would be the degree (depth) of the B-tree?.
What will determine the depth of the B-tree in a table/database?
Thanks in advance.
Chandhini
November 7, 2009 at 7:06 pm
Heh... why do you care? It's not like you'll be able to change it or take advantage of it.
--Jeff Moden
Change is inevitable... Change for the better is not.
November 7, 2009 at 9:25 pm
Chandhini (11/7/2009)
I have 10,000 records in a table.What would be the degree (depth) of the B-tree?.
Not enough information. Depends on the definition of the index in question and the column types of the table (and sometimes the data in those columns). Have a look at this for some info on indexes. http://www.sqlservercentral.com/articles/Indexing/68439/
Why are you asking?
Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability
November 7, 2009 at 11:07 pm
Chandhini (11/7/2009)
I have 10,000 records in a table.What would be the degree (depth) of the B-tree?.
What will determine the depth of the B-tree in a table/database?
If it is a real table, you can get the index depth by querying the sys.dm_db_index_physical_stats dynamic management view.
In general, the only thing that determines the index depth is the total number of rows, and the size of the index key (more specifically how many keys will fit on an 8,096 byte page).
With 10K rows in the table, there will be 10K rows in the leaf level (assuming this is not a filtered index). The maximum width of an index key is 900 bytes. Taking this as the worst-case scenario, each (non-leaf) page can contain a maximum of 8 index keys. So:
Leaf: 10K rows
Level 1: 10,000 / 8 = 1,250 pages
Level 2: 1,250 / 8 = 157 pages
Level 3: 157 / 8 = 20 pages
Level 4: 20 / 8 = 3 pages
Level 5: 3 / 8 = 1 page (root)
So, the index would have 6 levels, including the leaf.
If the key size were just 16 bytes, we could fit 506 index keys on a page:
Leaf: 10K rows
Level 1: 10,000 / 506 = 20 pages
Level 2: 20 / 506 = 1 page (root)
So in this case, there would be only 2 non-leaf levels.
For more details of B+ trees as used by SQL Server, see http://en.wikipedia.org/wiki/B%2B_tree
Paul
Paul White
SQLPerformance.com
SQLkiwi blog
@SQL_Kiwi
November 9, 2009 at 3:11 am
November 9, 2009 at 3:20 am
ta.bu.shi.da.yu (11/9/2009)
Jeff Moden (11/7/2009)
Heh... why do you care? It's not like you'll be able to change it or take advantage of it.That seems a bit rude!
I think it depends on how you read it; I read it imagining a smirking Jeff Moden...(it was the 'heh' that did it I think)...but I do see how it could be read otherwise :pinch:
Paul White
SQLPerformance.com
SQLkiwi blog
@SQL_Kiwi
November 9, 2009 at 3:58 am
Paul White (11/9/2009)
ta.bu.shi.da.yu (11/9/2009)
Jeff Moden (11/7/2009)
Heh... why do you care? It's not like you'll be able to change it or take advantage of it.That seems a bit rude!
I think it depends on how you read it; I read it imagining a smirking Jeff Moden...(it was the 'heh' that did it I think)...but I do see how it could be read otherwise :pinch:
It was the " It's not like you'll be able to change it or take advantage of it." It seemed like a pretty reasonable question to me! And the answer that was given later was quite interesting.
November 9, 2009 at 4:02 am
ta.bu.shi.da.yu (11/9/2009)
It was the " It's not like you'll be able to change it or take advantage of it." It seemed like a pretty reasonable question to me! And the answer that was given later was quite interesting.
I see - perhaps it could have used a 😛 or a 😉 ... I don't know. Jeff may well clarify later; though I expect it was probably intended to be ambiguous or sweet-and-sour!
Paul White
SQLPerformance.com
SQLkiwi blog
@SQL_Kiwi
November 9, 2009 at 4:25 am
Paul White (11/9/2009)
ta.bu.shi.da.yu (11/9/2009)
It was the " It's not like you'll be able to change it or take advantage of it." It seemed like a pretty reasonable question to me! And the answer that was given later was quite interesting.I see - perhaps it could have used a 😛 or a 😉 ... I don't know. Jeff may well clarify later; though I expect it was probably intended to be ambiguous or sweet-and-sour!
You know, given what I've seen of Jeff, I'm sure it was 🙂 Jeff seems to me to be a good guy, I've probably misread the post (or at the least read too much into it).
November 9, 2009 at 6:08 am
It was intended only as posted... I wanted to know why someone wanted to know this level of detail especially since I'm pretty sure they can't change it or take advantage of it. Perhaps I shouldn't have included the "Heh" so people would have known I really wanted to know. 😉
Heh... Remember our other conversation, Paul? Now you know why I usually include some sort of "not trying to be snarky here" disclaimer for things like this... I get held to a different level of expected response by the general community and I get shot at, a lot, because of it. I have to butter every dry logical question I ask and every dry logical response I post. Not complaining... just a fact. 😛
--Jeff Moden
Change is inevitable... Change for the better is not.
November 9, 2009 at 6:14 am
Jeff Moden (11/9/2009)
It was intended only as posted... I wanted to know why someone wanted to know this level of detail especially since I'm pretty sure they can't change it or take advantage of it. Perhaps I shouldn't have included the "Heh" so people would have known I really wanted to know. 😉
In that case, I apologise for not assuming good faith. No hard feelings Jeff?
November 9, 2009 at 9:15 am
You can determine this by set statistics IO on and running a single-row-hit select on the indexed column (that doesn't have to hit the base table). whatever you get is the depth.
I, like Jeff, would like to know why it matters to you.
Best,
Kevin G. Boles
SQL Server Consultant
SQL MVP 2007-2012
TheSQLGuru on googles mail service
November 9, 2009 at 12:34 pm
ta.bu.shi.da.yu (11/9/2009)
Jeff Moden (11/9/2009)
It was intended only as posted... I wanted to know why someone wanted to know this level of detail especially since I'm pretty sure they can't change it or take advantage of it. Perhaps I shouldn't have included the "Heh" so people would have known I really wanted to know. 😉In that case, I apologise for not assuming good faith. No hard feelings Jeff?
Nah... not a problem... short forum postings are difficult to interpret so far as mood, feeling, and voice go. I can definitely see where someone may have taken my post in a manner different than intended.
--Jeff Moden
Change is inevitable... Change for the better is not.
November 9, 2009 at 3:14 pm
TheSQLGuru (11/9/2009)
You can determine this by set statistics IO on and running a single-row-hit select on the indexed column (that doesn't have to hit the base table). whatever you get is the depth. I, like Jeff, would like to know why it matters to you.
That is a very clever way to do it. I like it!
...especially since it goes to show one reason why logical I/O is such a poor performance metric - a single row select on a heap requires 1 logical I/O, and the same select using a clustered index 8 levels deep needs 8 I/Os: is the clustered seek really 8 times slower? 😉
I don't suppose we will ever hear back, but maybe the OP was just curious? It's the sort of question that I could imagine intriguing me - not for any practical reason, just to enhance understanding. If nothing else, it illustrates how efficient balanced trees are, and also why SQL Server enforces a relatively small maximum index key size. That said, it could have been an exam/interview/homework question too 😀
Paul White
SQLPerformance.com
SQLkiwi blog
@SQL_Kiwi
November 9, 2009 at 3:57 pm
I think we answer quite a few exam/homework type questions. Sometimes they do evoke a good learning discourse though.
Best,
Kevin G. Boles
SQL Server Consultant
SQL MVP 2007-2012
TheSQLGuru on googles mail service
Viewing 15 posts - 1 through 15 (of 17 total)
You must be logged in to reply to this topic. Login to reply