B⁺-Tree Indexes

The most powerful of all database indexes is the B⁺-Tree index. It can use fixed or variable length keys and orders them in such a way as to allow multiple methods of searching, such as find first, last, greater than, less than as well as equal to. It is organized into pages that have much better read/write efficiency and it is also self-leveling. With its basic key design it can make use of most data formats, from integers, floating point, dates, text strings and so on.

The B⁺-Tree is similar in design to be B-Tree but each node has more than one key value and two pointers, in fact each page of the B⁺-Tree normally contains about 50 or so key values that are sorted from smallest to largest. Within each key value within the index nodes is a pointer that has the reference to the next page below the node. The search first obtains the head node, searches through the list of keys until it finds the first key greater than the desired key than moves onto the next node, if no key is greater than the search key, then the last page is referenced. Once the leaf page at the bottom of the index is found, the corresponding ObjectID can be obtained and the search in complete.

When a new key is inserted into the B⁺-Tree index, the search finds if the desired position is free, then if there is not enough room to fit the new key within the page is broken up into two, filling each new page with half of the contents of the old and placing a new key into the new page. This creates a data structure that expands sideways rather than vertically like the humble B-Tree.