Affordable Access

Access Structures

Authors

Abstract

Access Structures COMP3017 Advanced Databases Dr Nicholas Gibbins - [email protected] 2012-2013 1 Overview Index basics Sequential files Dense indexes Sparse indexes Multi-level indexes Secondary indexes Indirection B+trees Hash tables Index Basics Index basics Relations are stored in files Files are stored as collections of blocks Blocks contain records that correspond to tuples in the relation How do we find the tuples that match some criteria? Indexes Index Blocks containing records search value matching records Tuples of a relation are sorted by their primary key Tuples are then distributed among blocks in that order Common to leave free space in each block to allow for later insertions 10 20 30 40 50 60 70 80 90 100 110 120 Sequential Files data file Only two records per block – typically more No free space shown in blocks 6 To Index or Not To Index? Maintaining an index costs processor time When entries are added, index must be updated Index must be maintained to make good use of resources There is a trade off between: Rapid access when retrieving data Speed of updating the database Sequence of blocks holding only keys and pointers to records Entry for every record in data file Blocks of index are in same order as those of the data file Key-pointer pair much smaller than record Dense Index 10 20 30 40 50 60 70 80 90 100 110 120 ... ... ... 10 20 30 40 50 60 70 80 90 100 110 120 data file dense index Fewer blocks than data file, fewer disk accesses Keys are sorted, so can use binary search Can keep in main memory if small enough (no disk accesses) Dense Index 10 20 30 40 50 60 70 80 90 100 110 120 ... ... ... 10 20 30 40 50 60 70 80 90 100 110 120 data file dense index Sparse Index One key-pointer pair per block of data file Can only be used if data file is sorted by search key Uses less space than dense index Takes longer to find key than dense index 10 30 50 70 90 110 ... ... ... ... ...

There are no comments yet on this publication. Be the first to share your thoughts.