Lecture
Database management systems provide several types of indexes to improve performance and data integrity in various applications. Index types include b-trees , bitmap indexes , and r-trees .
In database management systems, the reverse key indexing strategy reverses the value of a key before it is entered into the index . For example, the value 245380 becomes 835420 in the index. Reversing the key value is especially useful for indexing data such as sequence numbers , where each new key value is greater than the previous one, i.e., the values increase monotonically. Reverse key indexes have become especially important in high-volume transaction processing systems, since they reduce contention for index blocks .
Reverse key indexes use b-tree structures, but the key values are preprocessed before being inserted. Put simply, b-trees place similar values in the same index block, for example storing 245380 in the same block as 245390. This makes them efficient both for finding a specific value and for finding values within a range. However, if an application inserts values sequentially, each insert has to access the newest block in the index in order to add the new value. If several users try to insert at the same time, they all have to write to that block and must queue up, which slows down the application. This is a particular problem in clustered databases , where the block may need to be copied from the memory of one computer to that of another so that the next user can perform the insert.
With key reversal, similar new values are spread throughout the index instead of being concentrated in any one leaf block. This means that 245380 ends up in the same block as 145380, while 245390 ends up in another block, eliminating this source of contention . (Since 145380 was created long before 245380, their inserts do not interfere with each other.)
Reverse indexes are just as efficient as ordinary indexes for finding specific values, although they are useless for range queries. Range queries are not common for artificial values such as sequence numbers. When searching the index, the query handler simply reverses the search target before looking it up.
Applications typically delete older data on average before deleting newer data. Thus, data with lower sequence numbers usually predates data with higher values. Over time, in standard b-trees the index blocks for lower values eventually come to hold a small number of values with a corresponding increase in unused space, called «rot». Rot not only wastes space but also reduces query speed, because a smaller portion of the rotted index's blocks fits in memory at any given time. In a b-tree, if 145380 is deleted, its index space remains empty. In a reverse index, if 145380 predates the arrival of 245380, then 245380 can reuse the space of 145380.
Comments