NEWS

Tuesday, April 13, 2010

Data allocation in B-tree

If a table has 10000 records.
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

No comments:

Post a Comment