The B-tree structure is the standard organization for indexes in a database system. There are several variations of the B-tree, the most well known being the B*-tree and the B+-tree. The B-tree guarantees at least 50% storage utilization, that is, at any given time, the tree has each of its nodes at least 50% full. The B+-tree is a slightly different data structure, which in addition to indexed access, also allows sequential data processing and stores all data in the lowest level of the tree.
B Trees are multi-way trees. That is each node contains a set of keys and pointers. A B Tree with four keys and five pointers represents the minimum size of a B Tree node. A B Tree contains only data pages.
B Trees are dynamic. That is, the height of the tree grows and contracts as records are added and deleted.
B+ Trees A B+ Tree combines features of ISAM and B Trees. It contains index pages and data pages. The data pages always appear as leaf nodes in the tree. The root node and intermediate nodes are always index pages. These features are similar to ISAM. Unlike ISAM, overflow pages are not used in B+ trees.
The index pages in a B+ tree are constructed through the process of inserting and deleting records. Thus, B+ trees grow and contract like their B Tree counterparts. The contents and the number of index pages reflects this growth and shrinkage.
B+ Trees and B Trees use a "fill factor" to control the growth and the shrinkage. A 50% fill factor would be the minimum for any B+ or B tree. As our example we use the smallest page structure. This means that our B+ tree conforms to the following guidelines.
As this table indicates each page must have a minimum of two keys. The root page may violate this rule.
The following table shows a B+ tree. As the example illustrates this tree does not have a full index page. (We have room for one more key and pointer in the root page.) In addition, one of the data pages contains empty slots.
Adding Records to a B+ Tree
The key value determines a record's placement in a B+ tree. The leaf pages are maintained in sequential order AND a doubly linked list (not shown) connects each leaf page with its sibling page(s). This doubly linked list speeds data movement as the pages grow and contract.
We must consider three scenarios when we add a record to a B+ tree. Each scenario causes a different action in the insert algorithm. The scenarios are:
Download your Full Reports for B Tree