Database Reference
In-Depth Information
Search for
data with key
value 60
Binary
Search Tree
34
06
8
12
60
44
3
15
21
11
48
01
81
23
Figure 12-14
Binary search tree.
left
pointer
data
pointer
key
value
right
pointer
51247
B-Tree
Index
left
pointer
data
pointer
key
value
right
pointer
left
pointer
data
pointer
key
value
right
pointer
31123
null
82928
left
pointer
data
pointer
key
value
right
pointer
left
pointer
data
pointer
key
value
right
pointer
left
pointer
data
pointer
key
value
right
pointer
null
21043
null
null
47374
null
null
92654
null
Data File
Figure 12-15
B-tree index.
represents the index entry at the middle of the index file. Figure 12-14 presents a
binary search tree for the example considered here.
Primary indexes adopt binary search techniques by arranging the index records
as nodes in a binary search tree. The lines pointing outward from each node repre-
sent pointers to the other nodes on either side. The search for an index record always
begins at the root node and then proceeds to the right or the left by following the
appropriate pointers.
B-Tree Index
Figure 12-15 shows the contents of each node in a B-tree index and illustrates how
the pointers trace the search for a particular record.
Each node contains two pointers for pointing to the index records on the left and
right sides. A node also contains a pointer to where the data for the particular key
value resides on data storage. These pointers are actually storage addresses. For
Search WWH ::
Custom Search