Skip to content

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

License

Notifications You must be signed in to change notification settings

skyzh/BPlusTree

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

46 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

BPlusTree

Build Status

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.

About

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

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages