Package org.apache.activemq.store.kahadb.disk.index

Class BTreeIndex<Key,​Value>

  • All Implemented Interfaces:
    Index<Key,​Value>
    public class BTreeIndex<Key,​Value>
extends Object
implements Index<Key,​Value>
    BTreeIndex represents a Variable Magnitude B+Tree in a Page File. A BTree is a bit flexible in that it can be used for set or map-based indexing. Leaf nodes are linked together for faster iteration of the values.
    The Variable Magnitude attribute means that the BTree attempts to store as many values and pointers on one page as is possible.
    The implementation can optionally a be Simple-Prefix B+Tree.
    For those who don't know how a Simple-Prefix B+Tree works, the primary distinction is that instead of promoting actual keys to branch pages, when leaves are split, a shortest-possible separator is generated at the pivot. That separator is what is promoted to the parent branch (and continuing up the list). As a result, actual keys and pointers can only be found at the leaf level. This also affords the index the ability to ignore costly merging and redistribution of pages when deletions occur. Deletions only affect leaf pages in this implementation, and so it is entirely possible for a leaf page to be completely empty after all of its keys have been removed. , $Date$