Understand about index page,B Tree

  • Hi,

    I am intermediate on MSSQL . There are many article related to index and Btree . Here i stuck with one question where this Btree structure been defined . In other articles/theories sql maintain index on index pages . When queering any data from any clustered table,sql will pick Btree details from index page ?

    Or in other words

    For example a 10M records on clustered table ,to find a particular record sql will use index . This index has many non leaf nodes ,where this been defineed. Please give me some more details..

    🙂

  • These may help

    http://www.sqlservercentral.com/articles/Indexing/68439/

    http://www.sqlservercentral.com/articles/Indexing/68563/

    http://www.sqlservercentral.com/articles/Indexing/68636/

    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

    We walk in the dark places no others will enter
    We stand on the bridge and no one may pass
  • sql crazy kid (6/29/2013)


    Hi,

    ...

    For example a 10M records on clustered table ,to find a particular record sql will use index . This index has many non leaf nodes ,where this been defineed...

    Nodes are (index) rows in non-leaf pages (page=8KB). In fact, the number of non-leaf pages is very few compared to number of leaf pages. So few, that the number of non-leaf pages is negligible.

    Let's make rough estimation for 10M rows:

    If leaf page fits 200 data rows on average, we have 10 000 000 / 200 = 50 000 leaf pages. If each non-leaf page fits 400 index records (each index record points to a PAGE of lower level), at the first level above leaf level we need 50 000 / 400 = 125 pages. The next level up will fit all 125 rows in one page.

    So, for 10M rows you would have just 2 levels deep index, with 50 000 leaf and 125+1 non-leaf pages.

    Number of non-leaf pages is much less than 1% of leaf pages, close to 0.2%. That's why indexes are very efficient and non-leaf pages are often cached in buffer pool.

    Just to have a better picture on ratios.

    _____________________________________________________
    Microsoft Certified Master: SQL Server 2008
    XDetails Addin - for SQL Developers
    blog.sqlxdetails.com - Transaction log myths
  • You will love DM function sys.dm_db_index_physical_stats.

    In DETAILED mode it gives you info about the index, level-by-level (0 = leaf level).

    Example:

    -- Create HEAP table and insert 10M rows in one step

    select top 10000000 a.*

    INTO BigTable

    from sys.all_columns a cross join sys.all_columns b

    -- create clustered index (table becomes "clustered", it is no longer HEAP)

    alter table BigTable add id int identity primary key clustered

    -- display index physcal details, level by level

    select *

    from sys.dm_db_index_physical_stats

    (db_id(), -- current db

    object_id('BigTable'),

    1, -- clustered index

    DEFAULT, -- default = all partitions

    'DETAILED' -- DETAILED (gives info by each index level), SAMPLED, LIMITED (fastest)

    )

    -- cleanup

    -- drop table BigTable

    And the result is:

    index_levelpage_countrecord_count

    010551510000000

    1170105515

    21170

    On leaf level (level 0) we have 10 000 000 rows in 105 515 data pages.

    On first non-leaf level (level 1) we have 105 515 index ROWS that fit in only 170 index PAGES.

    Above that, at level 2 is only one, a root page of the index containing 170 index rows (each index row points to a PAGE of the level below, so at level 1 we have 170 PAGES).

    Percent of Btree pages in total pages is (170+1) / (170+1+105515) = 0,16% which is well below 1%.

    Hope that helps a bit in understanding.

    _____________________________________________________
    Microsoft Certified Master: SQL Server 2008
    XDetails Addin - for SQL Developers
    blog.sqlxdetails.com - Transaction log myths

Viewing 4 posts - 1 through 3 (of 3 total)

You must be logged in to reply to this topic. Login to reply