This chapter covers indexing techniques ranging from the most basic one to highly specialized ones. Due to the extensive use of indices in database systems, this chapter constitutes an important part of a database course. A class that has already had a course on data-structures would likely be familiar with hashing and perhaps even B + -trees. However, this chapter is necessary reading even for those students since data structures courses typically cover indexing in main memory. | Chapter 12: Indexing and Hashing Rev. Sep 17, 2008 Database System Concepts, 5th Ed. ©Silberschatz, Korth and Sudarshan See for conditions on reuse Chapter 12: Indexing and Hashing s Basic Concepts s Ordered Indices s B+Tree Index Files s BTree Index Files s Static Hashing s Dynamic Hashing s Comparison of Ordered Indexing and Hashing s Index Definition in SQL s MultipleKey Access Database System Concepts 5th Edition. ©Silberschatz, Korth and Sudarshan Basic Concepts s Indexing mechanisms used to speed up access to desired data. q ., author catalog in library s Search Key attribute to set of attributes used to look up records in a file. s An index file consists of records (called index entries) of the pointer searchkey form s Index files are typically much smaller than the original file s Two basic kinds of indices: q Ordered indices: search keys are stored in sorted order q Hash indices: search keys are distributed uniformly across “buckets” using a “hash function”. Database System Concepts 5th Edition. ©Silberschatz, Korth and Sudarshan Index Evaluation Metrics s Access types supported efficiently. ., q records with a specified value in the attribute q or records with an attribute value falling in a specified range of values (. 10000 < salary < 40000) s Access time s Insertion time s Deletion time s Space overhead Database System Concepts 5th Edition. ©Silberschatz, Korth and Sudarshan Ordered Indices s In an ordered index, index entries are stored sorted on the search key value. ., author catalog in library. s Primary index: in a sequentially ordered file, the index whose search key specifies the sequential order of the file. q Also called clustering index q The search key of a primary index is usually but not necessarily the primary key. s .
