BPlusTree

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.
The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context — in particular, filesystems(In my repo, I use mmap.). This is primarily because unlike binary search trees, B+ trees have very high fanout (number of pointers to child nodes in a node, typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree.
In theory, if the size of the index node in B+ tree is close to the size of the disk block(eg.4k bytes page size in linux), a query operation needs to access the disk logb(N) times.

Feature

• Use mmap to read and write to disk.
• Use LRU to cache mapped blocks.

Benchmark

The above data was tested on my 2013 macbook-pro with Intel Core i7 4 cores 2.3 GHz.
Each record has a value length of 100 bytes and I set cache size to 5MB. See also test.

Build

make && ./test

API

BPlusTree(const char* path);
void Put(const std::string& key, const std::string& value);
bool Delete(const std::string& key);
bool Get(const std::string& key, std::string& value) const;
std::vector<std::string> GetRange(const std::string& left, const std::string& right) const;
bool Empty() const;
size_t Size() const;

TODO List

• Support for variable key-value length.
• When Dealloc is executed, put block into reuse-pool.
• Defragment db file.
• Add WAL(Write Ahead Log).
• Data compression.

Reference

[1] https://en.wikipedia.org/wiki/B%2B_tree
[2] https://www.cnblogs.com/nullzx/p/8729425.html
[3] http://man7.org/linux/man-pages/man2/mmap.2.html