Information Technology Reference
In-Depth Information
7.1
Sparse B-Tree Indexes
We assume that the physical database used to implement our logical database, that
is, the relation r.X;V/,isa
sparse B-tree
defined as follows:
1. The sparse B-tree is a tree whose nodes are database pages and whose root-to-leaf
paths are all of the same length; this length is called the
height
of the B-tree.
2. Each B-tree page p stores records with keys x satisfying
low-key
.p/
x<
high-key
.p/,
where
low-key
.p/ and
high-key
.p/ are fixed keys, called the
low key
and
high
key
, respectively, of page p. The low and high keys are not stored in the page; the
low key may appear as the least key in the records stored in the page, but this need
not be the case: the low key is just a lower bound on the keys stored in the page.
We s a y t h a t p a g e p
covers
the half-open key range Œ
low-key
.p/;
high-key
.p/.
3. The
level
of a B-tree page is one for a leaf page and one plus the level of its child
pages for a non-leaf page. For each level l
D
1;:::;h,whereh is the height of
the B-tree, the key ranges covered by the sequence of pages p
1
;:::;p
n
at level l
form a disjoint partition of the entire key space Œ
1
;
1
/,thatis,
low-key
.p
1
/
D1
,
low-key
.p
i
/<
high-key
.p
i
/
D
low-key
.p
iC1
/,fori
D
1;:::;n
1,
and
high-key
.p
n
/
D1
.
4. The leaf pages of the B-tree are data pages and store the tuples of r .
5. The non-leaf pages p of the B-tree are index pages and store
index records
of
the form .
low-key
.q/; q/,whereq is the page-id of a child page of page p.
There is one index record for each child page of page p. The child pages
of a B-tree page are ordered in ascending order by the low keys of the child
pages.
We say that such a tree structure b is a
sparse B-tree index on
relation r and that r
is the
logical database indexed by
B-tree b, denoted r
D
db
.b/.
Example 7.1
Figure
7.1
shows (a part of) a sparse B-tree index on relation r.X;V /
with tuples with keys 1, 3, 5, 6, 7, 9, 10, 11, 12, 14, 15, 17, 18, 19, 20, 21, 24, 25,
26, 27, etc. We assume (unrealistically) that only six tuples fit in a page. Pages p
4
to p
9
are leaf pages, p
2
and p
3
are index pages of height 2, and p
1
(of height 3) is
the root page.
t
We call a B-tree as defined above a
consistent B-tree
. This basic definition states
how the pages of the B-tree are organized as a tree structure and what key ranges are
covered by each page. The following lemma states the most important properties of
a consistent B-tree:
