Information Technology Reference
In-Depth Information
Fig. 11.1
Indexes on relation
r.X;Y;V /:(
a
) the leaf pages
of the sparse B-tree index on
primary key X ;(
b
) the leaf
pages of the dense secondary
B-tree index on Y
a
b
As noted earlier, some database management systems store the tuples of a
relation in an unordered file (heap), where the tuples, once inserted, remain in their
place until deleted or until the entire file structure is reorganized. In that case it is
customary that the index records in the secondary indexes are “hard pointers” to
the tuples, that is, of the form .y; .p; i //,where.p; i / is the tuple identifier of the
referenced tuple.
We assume here, as before, that the tuples are stored in the leaf pages of a sparse
B-tree index, which is a highly dynamic structure, with tuples moving from a page
to another in page splits and merges. With index records of the form .y; .p; i //,this
would mean constantly updating references in the secondary indexes. With index
records of the form .y;x;p/, on the contrary, the primary-key component x remains
valid when the tuple moves, and only the page-id component p turns invalid.
If the page-id components of index records are not updated when the referenced
tuples move, the page-id component can only be used as a guess of the current
location of the referenced tuple. In locating a tuple given a secondary-index record
.y;x;p/, we latch page p and inspect its contents so as to find out if the page is still
a data page that contains a tuple with primary key x. If not, the tuple is located from
the primary B-tree index by traversing it in search for key x.
The secondary indexes are updated at the end of the calls that implement the
forward-rolling insert and delete (and write) actions (Algorithms
6.7
and
6.8
)
or undo such actions (Algorithms
4.7
and
4.9
). For example, in the call
insert
.T;x;y;
v
/ that implements the insert action IŒx;y;
v
, the secondary index
is updated after inserting the tuple .x; y;
v
/ into data page p, unlatching the page
