[Home]B tree

HomePage | Recent Changes | Preferences

B+ tree data structures are the data structures most commonly found in databases and filesystems implementation. B+ enables amortized constant inserts and deletes.
B+ idea is that an inner node can have a variable number of sons within some pre-defined range. This leads to the relativly rear re-balancing of the tree, on contrary with AVL tree. The lower and upper watermarks are set ahead as for example, in B2-3 trees, where each node can have 2 or 3 sons.

Illegal state defined to be the state in which an inner node has illegal number of sons.

Inner node structures:
Each inner node has a separation values which divide between its sub-trees. For example, if some inner node has 3 sons (sub-trees) then it must have 2 separation values a1 and a2. All values less than a1 will be in the leftmost sub-tree, values between a1 and a2 will be found in the middle sub-tree, values greater than a2 will be in rightmost sub-tree.

Deletes:
If no inner node is in illegale state as a result of delete then finish.
If some inner node is in illegale state then one of two possible scenarios is true:

The action proceeds while either some node stays in legall state after delete or the root has one son, in which case its deleted.

Inserts:
If no inner node is in illegale state as a result of insert then finish
If some node has more than upper bound sons then split it into two nodes, each one with lower bound sons. And proceed the action recursivly in parent node.
The action stops when either a node is in legal state or root is split into two nodes and new root is inserted.

Searches:
Search is performed by following separation values to the tree leaves.

Notes:


HomePage | Recent Changes | Preferences
This page is read-only | View other revisions
Last edited November 27, 2001 5:11 pm by 128.139.197.xxx (diff)
Search: