If the value in a row is ???ABCD???, the value
for the reverse key index for that row is ???DCBA???.
To understand the need for a reverse key index, you have to review some basic facts
about the standard B*-tree index. First and foremost, the depth of the B*-tree is determined
by the number of entries in the leaf nodes. The greater the depth of the B*-
tree, the more levels of branch nodes there are and the more I/O is required to locate
and access the appropriate leaf node.
The index illustrated in Figure 4-1 is a nice, well-behaved, alphabetic-based index.
It??™s balanced, with an even distribution of entries across the width of the leaf pages.
But some values commonly used for an index are not so well behaved. Incremental
values, such as ascending sequence numbers or increasingly later date values, are
always added to the right side of the index, which is the home of higher and higher
values. In addition, any deletions from the index have a tendency to be skewed
toward the left side as older rows are deleted. The net effect of these practices is that
over time the index turns into an unbalanced B*-tree, where the left side of the index
is more sparsely populated than the leaf nodes on the right side.
Pages:
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222