Finding the height of the B-Tree of a table in SQL Server

Question

Since database data is organized in 8k pages in a B-tree, and likewise for PK information information, it should be possible for each table in the database to calculate the height of the B-Tree. Thus revealing how many jumps it takes to reach certain data.

Since both row size and PK size is of great importance, it is difficult to calculate since eg varchar(250) need not take up 250 bytes.

1) Is there a way to get the info out of SQL Server? 2) if not, is it possible to give a rough estimate using some code analyzing the tables of the db?

Arsenical

Do you even need to know the height? Isn't random access in a B-tree structure roughly O(log n) regardless? – Homoousian

Well, I've seen examples of really big primary keys.. such as 2 x GUID + 2 int. It would be interesting to see the penalty as so many fewer keys can be stored in each index page – Arsenical

Keep in mind that only tables with clustered indexes are stored as B-trees, if there is no clustered index then the table is stored as a heap. So what you really want to know is what is the height of the B-tree for the clustered index, thus the answer below for dm_db_index_physical_stats. – Ebonize

Answer 1

YES! Of course!

Check out the DMV = dynamic management views in SQL Server - they contain a treasure trove of information about your indices. The dm_db_index_physical_stats is particularly useful for looking at index properties...

If you run this query in AdventureWorks against the largest table - Sales.SalesOrderDetails with over 200'000 rows - you'll get some data:

SELECT 
    index_depth,
    index_level,
    record_count,
    avg_page_space_used_in_percent,
    min_record_size_in_bytes,
    max_record_size_in_bytes,
    avg_record_size_in_bytes
FROM
    sys.dm_db_index_physical_stats(DB_ID(), OBJECT_ID('Sales.SalesOrderDetail'), 1, NULL, 'DETAILED')

You'll get output for all index levels - so you'll see at one glance how many levels there are in the index (I have three rows -> three levels in the index). Index Level 0 is always the leaf level - where in the clustered index (index_id = 1) you have your actual data pages.

You can see the average, minimum and maximum record sizes in byte and a great deal of additional info - read up on DMV's, there's a great way to diagnose and peek into the inner workings of SQL Server!

Comedietta

can you please advice what is order size of this B Tree index? And how SQL server determines what order size to use? It's just from curiosity point of view. – Reflate

Answer 2

try this:

SELECT INDEXPROPERTY(OBJECT_ID('table_name'), 'index_name', 'IndexDepth')

Stokehole

Answer 3

from How many elements can be held in a B-tree of order n?

 (Average Number of elements that fit in one Leaf-node) * n ^ (depth - 1)

Arsenical