B-Trees have been the defacto standard for database indices for the 20th century and first 25 years of the 21st century. B-Trees are self-balancing tree data structure that maintains sorted data and allows searches, insertions, and deletions with a O(log n) time cost. The B-tree generalizes the BinarySearchTree#1.3.6.1.4.1.33097.1.0.1, allowing nodes to have more than two children.
| Operation | Asymptotic Cost |
|---|---|
| insert | O(log n) |
| delete | O(log n) |
| find | O(log n) |
| stream | O(n) |
O(u) is the space cost of an ArrayList.
BinarySearch#1.3.6.1.4.1.33097.0.0