数据库系统原理(英文)-12-11(精品·公开课件).ppt

May 2011 Database System Concepts - Chapter 12 Indexing and Hashing - PART 4 DATA STORAGE AND QUERY Chapter 12   Indexing and Hashing Contents in This Chapter Basic concepts about and classification of indexing ordered indices, hash indices Properties/types of ordered indices primary/clustering indices, secondary/non-clustering indices dense indices, sparse indices single-level indices, multi-level indices (e.g. B+-tree, B-tree) Hash indices hash functions static hash, dynamic hash §12.1 Basic Concepts How to locate records in DB file quickly? Indexing (索引技术) mechanisms used to speed up access to desired data e.g. for relation account(account-number, branch-name, balance) shown in Fig.12.1, the index branch-name ? physical address of record (i.e.tuple) in DB file account Search Key attributes or a set of attributes used to look up the records in a file e.g. branch-name §12.1 Basic Concepts (cont.) Indexing mapping from search-key to storage locations of the file records, i.e. search-key ? storage locations of the records in disks §12.1 Basic Concepts (cont.) Two basic kinds of indices: ordered indices: the index file is used to store the index entries in which the search key of the records and the address of the records are stored in sorted order hash indices: the “hash function” is used to map the the search key of the records to the address of the records the records are stored in the “buckets”, the number of the bucket is as the address of the records and is determined by the hash function §12.2 Ordered Indices DBS file with indexing mechanism include two parts : indexed file, in which data records are stored index file, in which index entries are included e.g. Fig.12.1 The indexed file can be organized as sequential file heap file hash file clustering file §12.1 Basic Concepts (cont.) Index file set of index entries of the form Index files are typically much smaller than the original file 12.2 Ordered Indi