Database Reference
In-Depth Information
Figure A1-21.
Illustrating an m-way Search Tree
The M-Way tree has the following properties (which are illustrated in Figure
A1-22
):
a.
Each node is of the form
P0, K0, P1, K1, . . . Pn-1, Kn-1, Pn
where P
o
, P
1
… P
n
are pointers to successor nodes and K
o
, K
1
…
K
n-1
are key values.
b.
The key values in a node are in ascending order so that K
i
£ K
i
+ 1
.
c.
All key values in nodes of the sub-tree pointed to by P
i
are less
than the key value K
i
.
d.
All key values in nodes of the sub-tree pointed to by P
i
are
greater than the key value k
i-1
.
e.
The sub-tree pointed to by P
i
are also m-way search trees.
Figure A1-22.
A Three-way Search Tree
