Database Reference
In-Depth Information
A1.7.1 Definition of B-tree
A B-tree of order m is an m-way search tree with the following properties:
a.
Except for the root and leaves, each node of the tree has at
least [m/2] sub-trees and no more than m sub-trees so that
[m/2] £ number of sub-trees £ m. Note: [x] º the smallest
integer greater than x (e.g. [1.5] = 2).
b.
The root of the tree has at least two sub-trees, unless it is
itself a leaf.
c.
All leaves of the tree are at the same level.
Figure
A1-23
illustrates a B-tree of order 3, constructed from the 3-way search tree of
Figure
A1-22
.
Figure A1-23.
B-tree of order 3 (Corresponding to 3-way Search Tree)
A1.7.2 Implementation of the B-tree
The main operations we desire for the B-tree include:
•
Creation
•
Direct Search
•
Sequential Search
•
Insertion
•
Deletion
