Computer Science › Section J · Database systems › Topic J.6
Traditional file structures: indexed and hash files
Long before modern database systems, programmers worked out how to lay records out in files so they could be found fast. Their two great ideas, indexing and hashing, still sit inside every serious DBMS.
Underneath the database
A DBMS presents tidy tables, but its data lives in files on mass storage, and their organisation decides how fast records can be found. Three traditional organisations matter. A sequential file is read from start to finish in order. An indexed file adds a separate list of keys and locations, like the index of a book. A hash file computes each record's location directly from its key. Each suits a different pattern of use.
Sequential files and logical records
In a sequential file, records are processed in the order they are stored, as if in one long row. Audio, video and text documents are usually sequential files. A file of records can be built by giving every record a fixed format: a sports club might store each member as 40 characters, a 32-character name padded with spaces followed by an 8-character member number. Each 40-character block is one logical record, and record \(n\) starts at character \(40(n-1)\), counting from 0, so record 7 starts at character 240. A program must also detect the end of the file, either by a special final record called a sentinel or from the file length the operating system records.
Master files and transaction files
Sequential files work best when records are kept in key order, such as by member number. A classic batch update uses two files sorted the same way. The master file holds the permanent records; a transaction file collects the period's changes, such as membership renewals, and is sorted to match. One pass through both files, side by side, applies every change with no searching. A related job is merging two sorted files into one. The merge algorithm also powers merge sort, described in "Recursive structures: binary search".
Worked example: merging two sorted files
File X holds keys 3, 8, 15 and file Y holds 5, 6, 20, 21. Steps: (1) Compare the current records, 3 and 5; output 3 and move X on to 8. (2) Compare 8 and 5; output 5 and move Y to 6. (3) Compare 8 and 6; output 6 and move Y to 20. (4) Compare 8 and 20; output 8 and move X to 15. (5) Compare 15 and 20; output 15. X is now at its end of file. (6) Copy the rest of Y, 20 and 21, to the output. Result: 3, 5, 6, 8, 15, 20, 21, after only five comparisons, with each input read once from start to end.
Indexed files
Sequential files are poor at fetching records in an unpredictable order: finding one member means reading past everyone stored before them. An indexed file solves this with an index, a list of the keys in the file, each paired with the location of its record. To fetch a record, look up its key in the index and then read that one location. The index normally lives in its own file beside the data and is copied into main memory when the data file is opened, so lookups are fast. The price is upkeep: every insertion or deletion must update the index as well as the data.
Worked example: what an index saves
A file holds 1,000,000 member records, and a program needs one of them. Steps: (1) Without an index, a sequential search reads records until it finds the right one: about 500,000 reads on average, and all 1,000,000 if the key is absent. (2) With an index sorted by key and held in memory, a binary search finds the key in at most \(\lfloor \log_2 n \rfloor + 1\) comparisons, which for a million is 20 (see "Recursive structures: binary search"). (3) The index gives the record's location, so one read fetches it. (4) So 20 fast memory comparisons and one read replace roughly half a million slow reads.
Indexes in layers
A large index can itself be too big to search comfortably, so indexes are often built in layers, forming a tree: a top-level index points to smaller indexes, which point to records. The directory system of an operating system works this way, with folders acting as indexes to subfolders and files (see "The memory manager and the file manager"). Database systems usually use a refinement called a B-tree, a balanced tree whose nodes each hold many keys, so that even a huge table can be searched in a handful of reads from storage.
Hash files
Hashing finds a record without searching an index at all. Storage is divided into buckets, each able to hold several records, numbered 0 up to one less than the number of buckets. A hash function converts each key into a bucket number, and the record is stored in that bucket. To retrieve it, apply the same function to the key, read that bucket and search its few records. A common hash function divides the key by the number of buckets and keeps the remainder. Text keys can be read as numbers via their character codes. On mass storage this gives a hash file; in main memory, the same idea gives a hash table.
Worked example: hashing into 13 buckets
A club hashes member numbers into 13 buckets using the remainder on division by 13. Steps: (1) 2041 = 13 × 157, remainder 0: bucket 0. (2) 3317 = 13 × 255 + 2: bucket 2. (3) 1150 = 13 × 88 + 6: bucket 6. (4) 4729 = 13 × 363 + 10: bucket 10. (5) 1306 = 13 × 100 + 6: bucket 6 again, a collision with 1150; both records share bucket 6. (6) Why 13 and not 10? With 10 buckets, keys that are multiples of 5, such as 15, 20, 35, 40, 55 and 70, give remainders 5, 0, 5, 0, 5, 0, crowding into two buckets. A prime bucket count shares no factor with such keys: with 11 buckets the same six land in 4, 9, 2, 7, 0 and 4.
Collisions, overflow and load factor
Collisions are practically unavoidable. With 30 buckets and a function that scatters keys at random, the chance that the first 7 records all land in different buckets is
so a collision is already more likely than not: the birthday problem again. When too many keys pile into some buckets, called clustering, those buckets fill and overflow, either growing or spilling into a reserved overflow area, and searches slow down. The load factor is the number of records divided by the file's total capacity. A common rule of thumb is that hash files work well below about 50% and degrade above about 75%, when the file is usually rebuilt larger.
Common mistakes to avoid
Counting record positions from 1 in the offset formula: record 1 starts at character 0. Thinking an index makes updates free; it must be maintained on every insertion and deletion. Assuming a good hash function prevents collisions; it only spreads them out. Choosing a bucket count with many factors, such as 10 or 40, which lets patterned keys cluster. Reading the load factor as records per bucket instead of records divided by total capacity.
Key takeaways
Sequential files are processed in order and suit batch work such as one-pass updates and merges. Indexed files keep a key-to-location list, usually in memory, giving fast lookups at the cost of upkeep; layered indexes and B-trees scale this up. Hash files compute a bucket from the key, often as the remainder on division by a prime number of buckets. Collisions are practically inevitable, so buckets must handle overflow, and performance falls as the load factor rises past about 75%.
Flashcards
Flashcard
A file processed in order from beginning to end
Test your understanding
Question 1 of 5
Records are 40 characters long and positions count from 0. At which character does record 5 begin?
Question 2 of 5
Using the remainder on division by 13, which bucket does key 3964 go into?
Question 3 of 5
Why is a prime number of buckets, such as 13, preferred to 10 for a division hash?
Question 4 of 5
A file holds 1,000,000 records with a sorted index in main memory. About how many index comparisons does a binary search need at most?
Question 5 of 5
A hash file has 50 buckets that each hold 4 records, and it now stores 160 records. What is its load factor, and what should happen?
