Database Reference
In-Depth Information
Review of Trees
This appendix provides a brief review of trees. You should pay specific attention to
the section on B-trees, since most DBMS suites implement them by default. Note: This
appendix is not meant to replace a full course (and text) in data structures. It should
therefore be regarded as an overview, not a final authority on the subject matter.
This review covers the following sub-topics:
•
Introduction to Trees
•
Binary Trees
•
Threaded Binary Trees
•
Binary Search Trees
•
Height-Balanced Trees
•
Heaps
•
M-way Search Trees and B-trees
•
Summary and Concluding Remarks
A1.1 Introduction to Trees
The main difference between O(N
2
) sorting algorithms and O(N log N) sorting algorithms
is that the latter repeatedly reduce (by approximately one half ) the number of keys
remaining to be compared with each other, while the former does not. Trees are excellent
sources of f (N log N) sorts.
As you are no doubt aware, in computer science, we use trees (and graphs) to represent
and implement complex data structures. Here is a working definition of a tree: A tree T is
a finite set of nodes (V
1
, V
2
…V
n
) such that:
a.
There is one designated node called the root
b.
The remaining nodes are partitioned into M ³ 0 disjoint sets
T
1
, T
2
…T
n
such that each T
i
is itself a tree.
c.
Except for the root, each node has a parent node.
