53 Dynamic B+Tree

A B+Tree can be regarded as an implementation technique for implementing a map<K,V> where K is the key type and V is the mapped value type.

We are particularly interested in an implementation that provides high performance for persistent maps, allowing for billions of (key,value) pairs.

It is assumed the keys are totally ordered. B+Trees support iteration of the (key,value) pairs in decreasing or increasing order of the keys. Unlike hashmaps this allows for efficient implementation of set theoretic operations (union, intersection and difference).

A B+tree is an m-ary tree with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves. The root may be either a leaf or a node with two or more children.

Three implementations

There are currently three implementations:

  • Ceda/cxUtils/BPlusTree.h (intended to be transient)
  • Ceda/cxPersistStore/BPlusTree.h (involves a huge macro named mImplementBplusTree)
  • Ceda/cxPersistStore/BPlusTree2.h, Ceda/cxPersistStore/src/BPlusTree2.cpp (uses TypeOps)

Here we are concerned with the dynamically typed one implemented in Ceda/cxPersistStore/BPlusTree2.h and Ceda/cxPersistStore/src/BPlusTree2.cpp.

Comment about existing complexity

The existing implementation seems very complex, and doesn't achieve a good separation of concerns.

Ideally we would separate out template classes that can go into a pure C++ header only library for implementing a B+Tree, without concern for persistence, type reflection etc.

Factor out the algorithms?

Let's start with the algorithm to search for a key in a given leaf node. This is currently a member function. It's pretty much implemented by the TypeOps on the key type. 

inline const TypeOps& Key(const CalculatedBTreeTypeInfo& bi)
{
    cxAssert(bi.m_keyType);
    return *bi.m_keyType;
}

ssize_t LeafNode::SearchLeaf(const _Key* key) const
{
    cxAssert(key);
    cxAssert(0 <= m_numKeyEntrys && m_numKeyEntrys <= MAX_NUM_LEAF_KEY_ENTRYS);
    const CalculatedBTreeTypeInfo& bi = GetCalculatedBTreeTypeInfo();

    return Key(bi).FindLast(
        cast_ptr<_KeyAndPayload>(m_entrys.data()),
        GetKeyAndPayloadSize(bi),
        m_numKeyEntrys,
        key);
}

Perhaps we should make this a free function and use generics over the LeafNode type. 

    template<typename LeatNode>
    ssize_t SearchBplusTreeLeafNode(const LeafNode& node, const _Key* key)
    {
        ...
    }

todo

  • Try to move more of the code into a pure C++ header only library
  • TypeOps provides enough alignment information to allow layout of std::pair<Key,cref> and std::pair<Key,Payload> to be predicted.
  • Remove ceda::pair and use std::pair instead, and use that layout
  • Confirm that xmap<short,int> or something like that works on ARMv7
  • Support bulk set theoretic operations (intersection, union and difference)

Links