The idea: where the records sit decides what is cheap
A table is stored on disk as a file of blocks (pages). The disk reads and writes whole blocks, so the cost of an operation is the number of block accesses: one read or one write of one block. A block of B bytes holds bfr = ⌊B / R⌋ records of R bytes (the blocking factor), so r records need b = ⌈r / bfr⌉ blocks. The file organization is the rule for which block a record goes into. The page stores the same 22 records three ways, with bfr = 3, and runs each operation on all three files.
On the canvas a frame turns orange when its block is read and blue when it is written. A matching record turns green; a new or moved record turns yellow. The score table counts the accesses as they happen.
The heap file: cheap to insert, slow to search
A heap file (unordered file) keeps records in the order they arrive. An insert reads the last block, adds the record and writes the block back: 2 accesses. A new block is started when the last one is full. But nothing tells you where a key is, so an equality search reads blocks from the first one until it finds the key: b/2 blocks on average, and all b when the key is not there. A range search always reads all b blocks. (Demo: find 61: 5 reads; Demo: find 29: all 8.)
The sorted file: binary search, costly inserts
A sorted file (ordered file) keeps the records in key order, so every block covers one stretch of keys. A binary search reads the middle block, compares the key with the block's first and last keys, and throws away half of the blocks: about log2 b reads. 61 takes 3 reads of 8 blocks; 29, which is missing, also takes 3, because the search stops when the block that would hold 29 does not. A range search is a binary search for the low end, then the next blocks in order, until a block ends at or past the high end. For 20–40 that is 4 reads, against 8 in the heap.
The price is paid on insert. The new record must go in its place, and every block is already full, so each later block passes its last record on to the next one: read it, write it. Inserting 40 into block 4 costs 1 read for the search plus 4 reads and 5 writes for the shift, 10 accesses. Inserting 8 at the front shifts the whole file: 18 accesses (Demo: insert 8). On average half the file is read and written. Textbooks avoid this with an unsorted overflow file that is merged into the sorted file now and then (a rebuild that is an external merge sort).
The hashed file and overflow chains
A hashed file has M buckets, here M = 7 with one block each, and a hash function h(k) = k mod 7 names the bucket of every record. A search computes h(k) in memory and reads that one block. When a bucket is full, the next record goes into an overflow block linked from the bucket, and the linked blocks form an overflow chain. A search then reads the chain until it finds the key, or to its end when the key is missing: bucket 1 holds 71 92 50 → 22 43, so finding 29 costs 2 reads.
A hash function scatters neighbouring keys over all buckets, so a range search must read every block of every bucket: 8 reads for 20–40, no better than the heap (Demo: range search 20–40). A static hash file also has a fixed M: as the file grows, chains grow and searches slow down. Dynamic schemes grow the number of buckets instead; see Extendible Hashing and Linear Hashing.
A sparse primary index on the sorted file
A primary index on a sorted file has one entry per data block: the block's first key, the anchor, and the block number. It is sparse: it does not list every record. An entry is much smaller than a record, so the index fits in far fewer blocks; here all 8 entries fit in one index block. To find a key, read the index, take the last anchor ≤ the key, and read that one data block. 61: anchor 50 → b5, 2 reads instead of 3 (Demo: sparse index: find 61).
The index must follow the data. When an insert shifts records, the first key of each later block changes, so the index block is written too: inserting 40 now costs 12 accesses, 2 more than without the index (Demo: sparse index: insert 40). With a big file the index itself has many blocks, and you search it with binary search, or put an index on the index. That multilevel index, kept balanced as it grows, is the B+ tree. An index with an entry for every record, which points to rows by their address, is on Database Index.
The costs side by side
| Operation | Heap file | Sorted file | Hashed file |
|---|---|---|---|
| Find a key | b/2 on average, b if missing | about log2 b (index: index blocks + 1) | 1 + overflow blocks read |
| Range search | b | search + the blocks in the range | every block |
| Insert | 2 | search + about b (half the file read and written) | chain reads + 1 or 2 writes |
And the demos, in block accesses (r = reads, w = writes):
| Demo | Heap | Sorted | Hashed |
|---|---|---|---|
| find 61 | 5 | 3 (index: 2) | 1 |
| find 29, missing | 8 | 3 | 2 |
| range 20–40, 6 records | 8 | 4 | 8 |
| insert 40 | 1 r + 1 w | 5 r + 5 w (index: 6 r + 6 w) | 1 r + 2 w |
| insert 8 | 1 r + 1 w | 10 r + 8 w | 2 r + 1 w |
What MariaDB actually uses
MariaDB does not let you choose "heap", "sorted" or "hashed" for a table. The storage engine decides:
- InnoDB (the default) stores every table as a clustered B+ tree on the primary key: the rows sit in the leaf pages in key order, and the inner pages are a multilevel sparse index. It is a sorted file that does not shift on insert: a full page splits into two half-full pages. See Clustered vs Secondary Index and Inside an InnoDB page.
- Aria and MyISAM keep the rows in a heap data file
(
.MAD/.MYD): a new row goes at the end, or into the space of a deleted row. Each index, the primary key too, is a separate B-tree in the index file (.MAI/.MYI) whose entries point to row positions in the data file. ALTER TABLE t ORDER BY colrewrites a MyISAM or Aria data file in key order once, like the sorted file here; later inserts and deletes do not keep that order. InnoDB ignores it, because its rows are always in primary key order.- Hashing appears only as an index type: the MEMORY engine's
HASHindex, and InnoDB's internal adaptive hash index. Neither is a hashed file on disk.
CREATE TABLE t_inno (id INT PRIMARY KEY, v CHAR(20)) ENGINE=InnoDB; -- clustered B+ tree on id CREATE TABLE t_aria (id INT PRIMARY KEY, v CHAR(20)) ENGINE=Aria; -- heap file + B-tree on id ALTER TABLE t_aria ORDER BY id; -- one-time sort of the data file
What the page leaves out
Deletes (a heap marks the slot free or moves the last record into it), variable-length and spanned records, and the file header that tells where the last block is. Real costs also depend on where blocks sit: reading neighbouring blocks in a row is much cheaper than random reads, and the buffer pool keeps hot blocks in memory. The overflow file for a sorted file, and how a rebuild merges it, are only mentioned. MariaDB has no static hashed file and no sorted file that stays sorted on insert; its engines use the B+ tree and heap files described above.