Database tables/indexes are typically stored in memory or on hard disk in one of many forms, ordered/unordered Flat files, ISAM, Heaps, Hash buckets or B+ Trees. These have various advantages and disadvantages discussed in this topic. The most commonly used are B+trees and ISAM.
Unordered storage typically stores the records in the order they are inserted, while having good insertion efficiency, it may seem that it would have inefficient retrieval times, but this is usually never the case as most databases use indexes on the primary keys, resulting in efficient retrieval times.
Ordered or Linked list storage typically stores the records in order and may have to rearrange or increase the file size in the case a record is inserted, this is very inefficient. However is better for retrieval as the records are pre-sorted (Complexity O(log(n))).
Structured files
Heaps
simplest and most basic method
insert efficient, records added at end of file – ‘chronological’ order
retrieval inefficient as searching has to be linear
deletion – deleted records marked
requires periodic reorganization if file is very volatile
advantages
good for bulk loading data
good for relatively small relations as indexing overheads are avoided
good when retrievals involve large proportion of records
disadvantages
not efficient for selective retrieval using key values, especially if large
sorting may be time-consuming
not suitable for ‘volatile’ tables
Hash buckets
Hash functions calculate the address of the page in which the record is to be stored based on one or more fields in the record
Hashing functions chosen to ensure that addresses are spread evenly across the address space
‘occupancy’ is generally 40% – 60% of total file size
unique address not guaranteed so collision detection and collision resolution mechanisms are required
open addressing
chained/unchained overflow
pros and cons
efficient for exact matches on key field
not suitable for range retrieval, which requires sequential storage
calculates where the record is stored based on fields in the record
hash functions ensure even spread of data
collisions are possible, so collision detection and restoration is required
B+ trees
These are the most used in practice.
the time taken to access any tuple is the same because same number of nodes searched
index is a full index so data file does not have to be ordered
Pros and cons
versatile data structure – sequential as well as random access
access is fast
supports exact, range, part key and pattern matches efficiently
‘volatile’ files are handled efficiently because index is dynamic – expands and contracts as table grows and shrinks
less well suited to relatively stable files – in this case, ISAM is more efficient
