Re: Index tree
From: Hugo Kornelis (hugo_at_pe_NO_rFact.in_SPAM_fo)
Date: 12/07/04
- Next message: Mark Allison: "Re: Need Dirxn --> How to schedule recurring stored procedure executio"
- Previous message: Mark Allison: "Re: how to decide about the database size"
- In reply to: Alan: "Index tree"
- Messages sorted by: [ date ] [ thread ]
Date: Tue, 07 Dec 2004 11:10:41 +0100
On Tue, 7 Dec 2004 15:03:09 +1100, Alan wrote:
>I can understand the number of table records will affect the width of the
>tree. But why it also affect the depth of the tree ? Or how the key size
>will afftect depth and width of the index tree ?
Hi Alan,
I'll use an example to explain. Let's assume you have a nonclustered index
with 800 bytes in the indexed columns and another 800 bytes in the
clustered key.
The leaf pages store both the indexed values and the corresponding values
in the clustered index (as locator to the actual row). Other pages (root,
intermediate) store only the indexed values. Since each page is about 8K,
a leaf page holds values for 5 rows; other pages have pointers for 10
rows.
If the number of rows in the table is 10, we need two leaf pages (assuming
no empty space, which will not always be the case in practice) to hold all
these rows. The root page will have the indexed values of the first row on
leaf page 1 and the first row on page 2; the rest of the root page remains
empty. This B-tree has depth 2 (root is level 1; leaf at level 2).
If we add another 40 rows for a total of 50, we need 10 leaf pages. The
root page will have the indexed values of the first row on each of these
10 leaf pages and no room to spare.
One extra row, bringing the total to 51, means we now need 11 leaf pages.
Since the root page can only point to max 10 pages, we need to add a
level. The new B-tree will have one root, two intermediate (level-2) and
11 data pages. One intermediate page will have the indexed values of the
first row on the first 5 or 6 leaf pages; the other intermediate page has
the indexed values of the first row on the remaining leaf pages; the root
page will only hold the indexed values of the first row of the two
intermediate pages. Note that we now have depth 3: root at level 1,
intermediate at level 2 and leaf at level 3.
We can now continue to add rows. When there are 500 rows, there are 100
leaf pages, 10 intermediate pages (each pointing to 10 leaf pages) and 1
root page (pointing to the 10 intermediate pages). All these pages are
completely full: when the 501st row is added, another level has to be
added to the index and it is now at depth 4.
The above shows how number of rows affects the B-tree depth. To see how
key size affects B-tree depth as well, imagine what happens if the indexed
columns are not 800 but 80 bytes: now you can store the indexed values of
not 10 but 100 rows in non-leaf pages. For the leaf pages, the capacity
would increase to (8K / (80 + 800)) = 9 rows. If the size of the clustered
index would decrease as well, this number would rise even further. This of
course means that you can add more rows until all leaf, intermediate and
root pages are full and another level has to be added.
Best, Hugo
-- (Remove _NO_ and _SPAM_ to get my e-mail address)
- Next message: Mark Allison: "Re: Need Dirxn --> How to schedule recurring stored procedure executio"
- Previous message: Mark Allison: "Re: how to decide about the database size"
- In reply to: Alan: "Index tree"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
