O'Reilly logo

Handbook of Data Structures and Applications, 2nd Edition by Sartaj Sahni, Dinesh P. Mehta

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

16

B Trees*

Donghui Zhang

Northeastern University

16.1Introduction

16.2The Disk-Based Environment

16.3The B-tree

B-tree DefinitionB-tree QueryB-tree InsertionB-tree Deletion

16.4The B+-tree

Copy-up and Push-upB+-tree QueryB+-tree InsertionB+-tree Deletion

16.5Further Discussions

Efficiency AnalysisWhy Is the B+-treeWidely Accepted?Bulk-Loading a B+-treeAggregation 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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required