B-tree's, blocks, pointers, ...?

Hi,
Is it correct that SQL Server (2000 and 2005) uses B-tree's for its indexes,
and not dense indexes nor sparse indexes? Or does it uses B+tree's?
What is the block size that it uses for B-tree's?
What is the pointer size that SQL Server uses?
Thanks a lot in advance,
PieterPieter
SQL Server 2005 (BOL)
ms-help://MS.SQLCC.v9/MS.SQLSVR.v9.en/udb9/html/b7d6b323-728d-4763-a987-92e6292f6f7a.htm
"Pieter" <pieterNOSPAMcoucke@.hotmail.com> wrote in message
news:O4oXUD2%23HHA.4200@.TK2MSFTNGP04.phx.gbl...
> Hi,
> Is it correct that SQL Server (2000 and 2005) uses B-tree's for its
> indexes, and not dense indexes nor sparse indexes? Or does it uses
> B+tree's?
> What is the block size that it uses for B-tree's?
> What is the pointer size that SQL Server uses?
> Thanks a lot in advance,
>
> Pieter
>|||To add on to the SQL 2005 Books Online reference Uri posted,
> What is the block size that it uses for B-tree's?
SQL Server uses 8K pages for data and index storage
> What is the pointer size that SQL Server uses?
The row locator size varies depending on whether or not the table has a
clustered index and if the key values are unique.
Clustered:
ms-help://MS.SQLCC.v9/MS.SQLSVR.v9.en/udb9/html/26b28045-c3c2-465a-b564-bf2189e93fdc.htm
Non-clustered:
ms-help://MS.SQLCC.v9/MS.SQLSVR.v9.en/udb9/html/1efeba1f-f848-4861-9af3-594e5ab3b597.htm
Hope this helps.
Dan Guzman
SQL Server MVP
"Pieter" <pieterNOSPAMcoucke@.hotmail.com> wrote in message
news:O4oXUD2%23HHA.4200@.TK2MSFTNGP04.phx.gbl...
> Hi,
> Is it correct that SQL Server (2000 and 2005) uses B-tree's for its
> indexes, and not dense indexes nor sparse indexes? Or does it uses
> B+tree's?
> What is the block size that it uses for B-tree's?
> What is the pointer size that SQL Server uses?
> Thanks a lot in advance,
>
> Pieter
>

b-tree structure.....

Can someone explain me or let me know the URL where I can find more details about b-tree structure.

I am more intrested in the calculation that is done in one of the articles below.

- Artcile -

With the 900 byte key, 8 rows can fit per database page. This means there will be 12500000 pages at the leaf level, 1562500 pages at the next level up in the b-tree and so on, giving a total of 12500000 + 1562500 + 195313 + 24415 + 3052 + 382 + 48 + 6 + 1 = 14285717 pages (including 1785717 to store the upper levels of the b-tree).

--

How is 1562500 , 195313 , 24415 etc are calculated.... from 12500000 leaf pages.

I suggest you acquire Kalen's book.

http://www.amazon.com/gp/product/0735609985/102-9365699-1188136?v=glance&n=283155|||

I have the book.

I didn't see anywhere in details talking about the b-tree allocation of pages in intermediate level, as I am looking for.

If you know, please let me know the page/ chapter in the book (may be i missed, I will look into it again).

thanks a lot,

ramanuj

|||

if you might have 8 values per page (since each value is 900 bytes and max page size is 8000 bytes) then for each tree level you'll have 8 times less space occupied since you need the pointers to the leafs on the next level.

So, 12500000 equals 1562500 times 8, 1562500 equals 195313 times 8 , etc....

|||

Approx. how many bytes are needed to hold each record details' (pointers) in intermediate pages, starting leaf page ?

What if I have 100 records per page, does it mean that intermediate pages would occupy 100 times less space @. each level ? How

|||

Each index entry has the following values:

- The clustered index

- The index key

So each record will ocupy the size of the clustered index, plus the sum of the sizes of the individual fields of the index key.

yes - if you have 100 records per page (or 80 bytes per each clustered index size + sum (index key columns) ) you'd have a tree where each level would have 100 less pages than the next

|||

Thanks for the info.

I am still looking forward to understand the intermediate pages content. I understand the leaf pages.

|||Ramanuj,

Kalen has dedicated the entire chapter 8 (page 405-) to index. You should get all of your questions answered there.

b-tree structure.....

Can someone explain me or let me know the URL where I can find more details about b-tree structure.

I am more intrested in the calculation that is done in one of the articles below.

- Artcile -

With the 900 byte key, 8 rows can fit per database page. This means there will be 12500000 pages at the leaf level, 1562500 pages at the next level up in the b-tree and so on, giving a total of 12500000 + 1562500 + 195313 + 24415 + 3052 + 382 + 48 + 6 + 1 = 14285717 pages (including 1785717 to store the upper levels of the b-tree).

--

How is 1562500 , 195313 , 24415 etc are calculated.... from 12500000 leaf pages.

I suggest you acquire Kalen's book.

http://www.amazon.com/gp/product/0735609985/102-9365699-1188136?v=glance&n=283155|||

I have the book.

I didn't see anywhere in details talking about the b-tree allocation of pages in intermediate level, as I am looking for.

If you know, please let me know the page/ chapter in the book (may be i missed, I will look into it again).

thanks a lot,

ramanuj

|||

if you might have 8 values per page (since each value is 900 bytes and max page size is 8000 bytes) then for each tree level you'll have 8 times less space occupied since you need the pointers to the leafs on the next level.

So, 12500000 equals 1562500 times 8, 1562500 equals 195313 times 8 , etc....

|||

Approx. how many bytes are needed to hold each record details' (pointers) in intermediate pages, starting leaf page ?

What if I have 100 records per page, does it mean that intermediate pages would occupy 100 times less space @. each level ? How

|||

Each index entry has the following values:

- The clustered index

- The index key

So each record will ocupy the size of the clustered index, plus the sum of the sizes of the individual fields of the index key.

yes - if you have 100 records per page (or 80 bytes per each clustered index size + sum (index key columns) ) you'd have a tree where each level would have 100 less pages than the next

|||

Thanks for the info.

I am still looking forward to understand the intermediate pages content. I understand the leaf pages.

|||Ramanuj,

Kalen has dedicated the entire chapter 8 (page 405-) to index. You should get all of your questions answered there.