B-Tree

Saturday morning algorithms practice: I implemented insert() and find() members std::map<> as a B-tree.

Each node in the B-tree has at most 2*t-1 keys and at most 2*t children. The best-case depth of a B-tree is log_{2*t}(N) and the worst case is log_{t}(N). During a search, O(2t) comparisons are performed per node, and O(height) nodes are visited.

For t = 3, my implementation shows the following complexity for searching:

N = 1000
Average nodes visited: 4.68
log_3(N) = 6.28771  (worst)
log_6(N) = 3.85529  (best)
tree depth = 5

For N = 25000, you may compare to an earlier implementation of skiplists.

N = 25000
Average nodes visited: 7.68968
log_3(N) = 9.21766  (worst)
log_6(N) = 5.65178  (best)
depth = 8