Introduction
B+ trees offer significant value by providing efficient data retrieval in block-oriented storage
applications like
file systems and databases. A B+ tree is nothing more than a tree (with a particularly high fanout or order,
which we
shall refer to as m) that satisfies the following conditions:
- An internal node (nodes that aren't the root or leaves) must have a number of children d such that ⌈m/2⌉
≤ d ≤ m.
- The root node may have at least 2 children and up to m children.
- The number of keys k that an internal node may carry is ⌈m/2⌉ - 1 ≤ k ≤ m - 1.
- Leaf nodes have no children, but the number of dictionary pairs k that a single leaf node may carry is
⌈m/2⌉ - 1 ≤ k ≤ m - 1.
- A B+ tree is similar to a B tree except that all the dictionary pairs lie in the leaf nodes.
Here is the implementation of B+ trees Click
Here
For the program to work properly, ensure that the input_file follows the format:
- The first line must contain Initialize(m) where m is the order of the B+ tree.
- All subsequent lines may contain only the following operations:
- Insert(key, value) where key is an integer and value is a floating point number.
- Delete(key) where key is the key of the dictionary pair you would like to delete.
- Search(key) where key is the key of the dictionary pair whose value you would like to find.
- Search(lowerBound, upperBound) where all values of dictionary pairs whose keys fall within
lowerBound ≤ key ≤ upperBound will be recorded.
Output for each search query will be recorded within a file titled output_file.txt.
Time and Space Complexity
| Operation |
Time Complexity |
Space Complexity |
| Insert |
O(logm n) |
O(n) |
| Delete |
O(logm n) |
O(n) |
| Search |
O(logm n) |
O(1) |