Đang chuẩn bị liên kết để tải về tài liệu:
Lecture Database system concepts (6/e): Chapter 11 - Silberschatz, Korth, Sudarshan

Chapter 11 - Indexing and hashing. 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 11: Indexing and Hashing Database System Concepts, 6th Ed. ©Silberschatz, Korth and Sudarshan See www.db-book.com for conditions on re-use Chapter 12: Indexing and Hashing Basic Concepts Ordered Indices B+-Tree Index Files B-Tree Index Files Static Hashing Dynamic Hashing Comparison of Ordered Indexing and Hashing Index Definition in SQL Multiple-Key Access Database System Concepts - 6th Edition 11.2 ©Silberschatz, Korth and Sudarshan Basic Concepts Indexing mechanisms used to speed up access to desired data. E.g., author catalog in library Search Key - attribute to set of attributes used to look up records in a file. An index file consists of records (called index entries) of the form search-key pointer Index files are typically much smaller than the original file Two basic kinds of indices: Ordered indices: search keys are stored in sorted order Hash indices: search keys are distributed uniformly across “buckets” using a “hash function”. Database System Concepts - 6th Edition 11.3 ©Silberschatz, Korth and Sudarshan Index Evaluation Metrics Access types supported efficiently. E.g., records with a specified value in the attribute or records with an attribute value falling in a specified range of values. Access time Insertion time Deletion time Space overhead Database System Concepts - 6th Edition 11.4 ©Silberschatz, Korth and Sudarshan Ordered Indices In an ordered index, index entries are stored sorted on the search key value. E.g., author catalog in library. Primary index: in a sequentially ordered file, the index whose search key specifies the sequential order of the file. Also called clustering index The search key of a primary index is usually but not necessarily the primary key. Secondary index: an index whose search key specifies an order different from the sequential order of the file. Also called non-clustering index. Index-sequential file: ordered .