Course Database Management Systems - Chapter 2: Indexing Structures for Files - Nguyen Thanh Tung

Nội dung text: Course Database Management Systems - Chapter 2: Indexing Structures for Files - Nguyen Thanh Tung

1. Chapter outline  Types of Single-level Ordered Indexes  Primary Indexes  Clustering Indexes  Secondary Indexes  Multilevel Indexes  Dynamic Multilevel Indexes Using B-Trees and B+-Trees  Indexes on Multiple Keys 2
2. Indexes as Access Paths (cont.)  The index file usually occupies considerably less disk blocks than the data file because its entries are much smaller  A binary search on the index yields a pointer to the file record  Indexes can also be characterized as dense or sparse.  A dense index has an index entry for every search key value (and hence every record) in the data file.  A sparse (or nondense ) index, on the other hand, has index entries for only some of the search values 4
3. Types of Single-Level Indexes Primary Index  Defined on an ordered data file  The data file is ordered on a key field, includes one index entry for each block in the data file; the index entry has the key field value for the first record in the block, which is called the block anchor  A similar scheme can use the last record in a block.  A primary index is a nondense (sparse) index, since it includes an entry for each disk block of the data file and the keys of its anchor record rather than for every search value. 6
4. Types of Single-Level Indexes Clustering Index  Defined on an ordered data file  The data file is ordered on a non-key field unlike primary index, which requires that the ordering field of the data file have a distinct value for each record.  Includes one index entry for each distinct value of the field; the index entry points to the first data block that contains records with that field value.  It is another example of nondense index where insertion and deletion is relatively straightforward with a clustering index. 8
5. Clustering index with a separate block cluster for each group of records that share the same value for the clustering field. 10
6. A dense secondary index (with block pointers) on a nonordering key field of a file. 12
7. A two-level primary index resembling ISAM (Indexed Sequential Access Method) organization. 16
8. Dynamic Multilevel Indexes Using B- Trees and B+-Trees  Because of the insertion and deletion problem, most multi-level indexes use B-tree or B+-tree data structures, which leave space in each tree node (disk block) to allow for new index entries  These data structures are variations of search trees that allow efficient insertion and deletion of new search values.  In B-Tree and B+-Tree data structures, each node corresponds to a disk block.  Each node is kept between half-full and completely full. 20
9. Difference between B-tree and B+-tree  In a B-tree, pointers to data records exist at all levels of the tree  In a B+-tree, all pointers to data records exist at the leaf-level nodes  A B+-tree can have less levels (or higher capacity of search values) than the corresponding B-tree 22
10. 23*0.69 = 15.87 ≈ 16 26
11. 34*0.69 = 23.46 ≈ 23 31*0.69 = 21.39 ≈ 21 28
12. An example of deletion from a B+-tree. 30