B-trees
A B-tree is a self-balancing tree data structure through which you can organize search, insertion, deletion, and sequential access in logarithmic time. For some operations, the time is not always logarithmic. In the previous chapter, we learned about the time complexity of the std::vector container’s push_back() function. When calculating it, we mentioned that it was amortized, O(1). The same happens for B-trees. Performing deletion and insertion on a B-tree takes amortized O(log n) time. The B-tree is a generalization of the binary search tree that allows nodes to have multiple children. The number of children and keys that a node of a B-tree can hold depends on what order it is in. According to Knuth’s definition, a B-tree of order m is a tree that satisfies the following properties:
- Every node has at most m children
- Every internal node has at least {m/2} children
- Every non-leaf node has at least two children
- All leaves appear on the same...