A simple B+ tree implemented in cpp. Fully unit-tested.
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
Number of pages in memory must be larger than those required for a single search, because page swapping is done after one operation.
- 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.