This unbalanced
growth has the overall effect of having an unnecessarily deep B*-tree structure, with
the left side of the tree more sparsely populated than the right side, where the new,
larger values are stored. The effects described here also apply to the values that are
automatically decremented, except that the left side of the B*-tree will end up holding
more entries.
Youcan solve this problem by periodically dropping and re-creating the index. However,
you can also solve it by using the reverse value index, which reverses the order
of the value of the index. This reversal causes the index entries to be more evenly distributed
over the width of the leaf nodes. For example, rather than having the values
234, 235, and 236 be added to the maximum side of the index, they are translated to
the values 432, 532, and 632 for storage and then translated back when the values
are retrieved. These values are more evenly spread throughout the leaf nodes.
The overall result of the reverse index is to correct the imbalance caused by continually
adding increasing values to a standard B*-tree index.
Pages:
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223