B+ trees are order “m” trees, often with a variable number of children per node. Unlike other such trees, in B+ trees, the internal nodes store only keys, while key-value pairs are stored in the leaf nodes.
In this project, a C++ implementation of a memory-resident B+ tree is presented. The implementation makes use of the Standard Template Library (STL), but does not use any of the complex data structures provided by it. The design is such that each key can have multiple values associated with it. Also, all leaf nodes are linked together to form a doubly linked list.
- Insert a key-value pair:
Insert(key,value) - Return all values associated with a given key:
Search(key) - Return all key value pairs in a given range:
Search(key1,key2)
The program expects input to be provided in a text file. The first line of this input file should specify the order of the B+ tree. Subsequent lines can have any of the above supported operations, one operation per line. A sample input file (input_file.txt) is provided.
The B+ tree output for search queries will be written in to output_file.txt
To build the source code: make
To execute the built binary: treesearch <input_file.txt>
To clean the repo: make clean