skyzh / bplustree

🌲 Fully unit-tested B+ tree with basic paging implemented in C++

BPlusTree

A simple B+ tree implemented in cpp. Fully unit-tested.

Implementations

BTree.cpp is automatically generated with source file from src/ folder. For original implementation, you should refer to src/.

Container: some basic containers implementation including Vector and Set.

LRU: least recently used cache, eliminating memory usage when processing huge chunks.

Persistence: manage so-called 'pages', which store BTree data.

Iterator: B+Tree iterators

Partially ported to upstream https://github.com/peterzheng98/CS158-DS_Project

Limitations

Number of pages in memory must be larger than those required for a single search, because page swapping is done after one operation.

Todo

• Reduce overhead in serialize and deserialize by passing istream as argument
• 4k align
• Reduce page offload overhead by introducing read-only page request
• Use HashMap to store pages in memory to store larger dataset.
• Implement copy constructor and assign
• Implement iterator and const iterator
• Reuse deleted pages
• Port to upstream: size, empty, iterator, return value of query and insert.