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.

The same 22 keys, 3 per block. Heap file: 8 blocks in insert order, 45 12 71, 27 63 18 and so on, the last block holds only 43. Sorted file: 8 blocks in key order, 12 14 16 up to 92. Hashed file: 7 buckets chosen by k mod 7; bucket 1 holds 71 92 50 and an overflow block 22 43
One set of records, three placements: insert order, key order, or the bucket a hash function picks.

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.

Bucket 5 holds 12 82 61 and is full. Insert 40, with 40 mod 7 = 5: read the bucket block, write a new overflow block holding 40, and rewrite the bucket block so its pointer links to the new block: 1 read and 2 writes. Afterwards a search in bucket 5 may read 2 blocks
An insert into a full bucket adds an overflow block, and every later search in that bucket may read one more block.

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).

One index block with 8 entries 12, 18, 27, 39, 50, 63, 76, 92, each pointing to data block b1 to b8. To find 61, the last anchor not greater than 61 is 50, so only block b5, holding 50 58 61, is read: 1 index read plus 1 data read
One entry per block is enough when the file is sorted: the anchor tells you which block a key must be in.

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

OperationHeap fileSorted fileHashed file
Find a keyb/2 on average, b if missingabout log2 b (index: index blocks + 1)1 + overflow blocks read
Range searchbsearch + the blocks in the rangeevery block
Insert2search + about b (half the file read and written)chain reads + 1 or 2 writes

And the demos, in block accesses (r = reads, w = writes):

DemoHeapSortedHashed
find 6153 (index: 2)1
find 29, missing832
range 20–40, 6 records848
insert 401 r + 1 w5 r + 5 w (index: 6 r + 6 w)1 r + 2 w
insert 81 r + 1 w10 r + 8 w2 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 col rewrites 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 HASH index, 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.

On the mind map

Open the Databases & Storage mind mapDatabases& StorageSchema and storage: how rows land on diskSchema and storageIndexes: find rows without a full scanIndexesRunning a query: parse, plan, executeRunning a queryCost-based optimizer: estimate rows, pick cheapest planCost-based optimizerQuery rewrites: same answer, simpler queryQuery rewritesTransactions: ACID: isolation and recoveryTransactionsApps and connections: the client side of the databaseApps and connectionsMongoDB: documents, replica sets, shardsMongoDBHow MySQL runs a queryHow MySQL runs a querybuffer pool, undo, redo, binlogHow PostgreSQL runs a queryHow PostgreSQL runs a querynew tuple per update, VACUUM, WALSELECT clause orderSELECT clause orderFROM, WHERE, GROUP BY, HAVING, SELECTJoin algorithmsJoin algorithmsnested loop, hash, merge: pick by sizeExternal merge sortExternal merge sort2N I/Os per pass, merge B−1 runs at onceFile organizationsHeap inserts, sorted ranges, hash findsMySQL JOIN, GROUP, ORDERMySQL JOIN, GROUP, ORDERtemporary table and filesortPostgres JOIN, GROUP, ORDERPostgres JOIN, GROUP, ORDERHashAggregate or Sort, by work_memRelational algebraRelational algebraselect, project, join: tables in, table outSQL joins on rowsSQL joins on rowsOuter joins pad unmatched rows with NULLSQL subqueriesSQL subqueriesOne NULL makes NOT IN return no rowsTriggers and proceduresTriggers and proceduresPer row; a CALL is not one statementWindow functionsWindow functionsaggregate per row without collapsingOpen the Databases & Storage mind mapDatabases & Storageparse, plan, executeRunning a queryHow MySQL runs a queryHow MySQL runs a querybuffer pool, undo, redo, binlogHow PostgreSQL runs a queryHow PostgreSQL runs a querynew tuple per update, VACUUM, WALSELECT clause orderSELECT clause orderFROM, WHERE, GROUP BY, HAVING, SELECTJoin algorithmsJoin algorithmsnested loop, hash, merge: pick by sizeExternal merge sortExternal merge sort2N I/Os per pass, merge B−1 runs at onceFile organizationsHeap inserts, sorted ranges, hash findsMySQL JOIN, GROUP, ORDERMySQL JOIN, GROUP, ORDERtemporary table and filesortPostgres JOIN, GROUP, ORDERPostgres JOIN, GROUP, ORDERHashAggregate or Sort, by work_memRelational algebraRelational algebraselect, project, join: tables in, table outSQL joins on rowsSQL joins on rowsOuter joins pad unmatched rows with NULLSQL subqueriesSQL subqueriesOne NULL makes NOT IN return no rowsTriggers and proceduresTriggers and proceduresPer row; a CALL is not one statementWindow functionsWindow functionsaggregate per row without collapsing
This page on the Databases & Storage mind map · 55 pages in 8 branches · open it to see the whole map and test yourself in recall mode.