Handbook of Data Structures and Applications, 2nd Edition

16

B Trees*

Donghui Zhang^†

Northeastern University

16.1Introduction

16.2The Disk-Based Environment

16.3The B-tree

B-tree Definition•B-tree Query•B-tree Insertion• B-tree Deletion

16.4The B+-tree

Copy-up and Push-up•B+-tree Query•B+-tree Insertion•B+-tree Deletion

16.5Further Discussions

Efficiency Analysis•Why Is the B+-treeWidely Accepted?•Bulk-Loading a B+-tree•Aggregation Query in a B+-tree

References

16.1Introduction

We have seen binary search trees in Chapters 3 and 11. When data volume is large and does not fit in memory, an extension of the binary search tree to disk-based environment is the B-tree, originally invented by Bayer and McCreight [1]. In fact, since the B-tree is always balanced (all leaf nodes appear at the same level), it ...