November 12, 2010 at 5:29 pm
Does anyone know the reasoning behind the max size being 900 bytes?
I understand having a large size index key (especially equal or larger than the size of a page) defeats the purpose of having an index, but why 900 bytes?
Since each node is a page...
Assuming all my index keys are 900 bytes, 8 indexes can fit in a node.
This leaves me with 800 bytes. I'm assuming 100 bytes per index key is needed to store the pointer to next level node or leaf.
Is 8 keys per node for a B-Tree considered a performance threshold?
November 13, 2010 at 2:48 am
caladba (11/12/2010)
Does anyone know the reasoning behind the max size being 900 bytes?
Could just be one of those chose numbers from early, early in history. Might have something to do with powers of 2 and the mathematical theory behind a b-tree
This leaves me with 800 bytes. I'm assuming 100 bytes per index key is needed to store the pointer to next level node or leaf.
No. A page pointer is 6 bytes. 2 bytes for fileID, 4 bytes for PageNo. There's other stuff as well (row headers, etc) but they're all small.
Is 8 keys per node for a B-Tree considered a performance threshold?
Personally I'd say it's well over. With a 900 byte key I can have in index 8 levels deep with only 20000 rows. That's waaaay deeper than is healthy. Deeper the index, more page reads and computation necessary to find an index, less useful overall the index is.
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 14, 2010 at 8:45 pm
GilaMonster (11/13/2010)
With a 900 byte key I can have in index 8 levels deep with only 20000 rows.
How? Using 900 byte keys, each (non-leaf) 8096-byte index page can contain a maximum of 8 index keys:
Leaf: 20,000 rows
Level 1: 20,000 / 8 = 2,500 pages
Level 2: 2,500 / 8 = 313 pages
Level 3: 313 / 8 = 40 pages
Level 4: 40 / 8 = 5 pages
Level 5: 5 / 8 = 1 page (root)
That's six levels (including the root).
I think we'd need 2,097,153 rows as a minimum:
Leaf: 2,097,153 rows
Level 1: 2,097,153 / 8 = 262,145 pages
Level 2: 262,145 / 8 = 32769 pages
Level 3: 32769 / 8 = 4097 pages
Level 4: 4097 / 8 = 513 pages
Level 5: 513 / 8 = 65 pages
Level 6: 65 / 8 = 9 pages
Level 7: 1 / 8 = 1 page (root)
Purely academic - such wide keys are a crazy idea.
Paul
November 14, 2010 at 10:05 pm
Need to check. Was 7 levels + leaf, that I know, was not 2 million rows, that I also recall. May have had an include, can't recall. Was for a post here
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 14, 2010 at 10:14 pm
I should check details before posting. the 20000 I remembered was page count, not row count.
900 byte key + 500 byte include. 96000 rows. 19001 pages in leaf. 8 levels (including leaf and root)
Still, a 6-level deep index is sick enough
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 14, 2010 at 10:17 pm
GilaMonster (11/14/2010)
Need to check. Was 7 levels + leaf, that I know, was not 2 million rows, that I also recall. May have had an include, can't recall. Was for a post here
Yup, had a heavy INCLUDE:
http://www.sqlservercentral.com/Forums/FindPost1019583.aspx
Sick indeed 🙂
Viewing 6 posts - 1 through 5 (of 5 total)
You must be logged in to reply to this topic. Login to reply