Databases Reference
In-Depth Information
byte page addressing or 256 records per page. New RID designs emerged over the past
decade using 6 and 8 byte designs. The specific format of RIDs varies between data-
bases, but the humble RID remains the essential device within the database for specify-
ing exactly where a record resides.
2.5
Summary
This chapter discussed the basic concepts in indexing, in particular the B+tree index
and composite index variation of the B+tree. A simple approach to estimating database
performance is used to aid in the tradeoff analysis.
TIPS AND INSIGHTS FOR DATABASE PROFESSIONALS
•
Tip 1. The B+tree is the indexing method of choice for all the major DBMSs.
Indexing should always be used for access to a small number of rows for queries.
•
Tip 2. Index tradeoff analysis can be done with a simple database performance
estimation mentioned above. This helps us justify index selection decisions.
Once we understand the basic performance model (see Appendix A) it can be easily
applied to any index mechanism so decisions on indexing can be based on actual
time to process a set of queries.
•
Tip 3. Remember that indexes have a cost.
Indexes provide orders of magnitude
benefit for query processing but that benefit comes with two significant penalties.
First storage cost. Every index that is created requires disk space to store the keys,
RIDs, pointers and intermmediate nodes. If several indexes are created on a table
the storage needs for the index structures can rival or even exceed the storage
requirements fore the data tables! Similarly indexes consume memory as well. Sec-
ondly, indexes need to be maintained as data is added deleted or updated from the
table. A simple change in the table data cane require an index key to not only be
modified, but to move from one leaf node to another requiring several times the I/O
and CPU processing that was required to simply modify the data in the base table.
As a result, while indexes have tremendous benefit for query performance, they also
impose a significant penalty on write operations such as INSERT, UPDATE,
DELETE, IMPORT and LOAD.
2.6
Literature Summary
The idea for extending a table for usage efficiency came from Scholnick [1980]. Com-
prehensive surveys of search methods can be found in Harbron [1988], Groshans
