Re: bitmap index Q.

At 03:48 PM 5/1/00 -0800, Ian MacGregor wrote:
>
>Lets sat you have a leaf node containing keys 1-9. In order to
>accomodate key 10
>it is necessary to split the block. This operations leaves keys 1-5 in
>the first block and keys 6-10 in the second block. The first block will
>never have another key entered into it. The same thing will happen to
>the second, third, etc as values are entered. Using only 50% of the
>space in means more splits, more splits mean move ripples up to the root
>of the tree, which means a deep narrow index.

Not true, actually.

Using your example, if you label the first block "A", and the left and right children "B" and "C", then if inserts cause "B" to grow to 10 keys, the 11th insert will cause this:

• "B" will be split into two nodes: "D", and "E". "B" gets re-used as one of the two.
• The first 5 keys from "B" will go into "D"
• The last 5 keys from "B" will go into "E"
• The 'middle' key will be promoted into block "A".

Now, block "A" has two keys, and points to 3 leaf nodes. On the average, leaf nodes will be 75% full, if you do mostly inserts. (If you do a lot of deletes, the average will be in the range 50-75%)

This will keep happening until "A" has 10 keys and an 11th is promoted into "A". Then "A" goes through the splitting procedure, and a new root node is created. This is why btrees are innately balanced -- the creation of new blocks happens from the top, not from the bottom.

---
Dennis Taylor
---
The opinions expressed herein are mine. Get your own opinions!