Skip to content
Tutorials Center
My learning

Topics

Lesson 51 of 79 ยท Storage and Indexing

File Organization: Heap, Sorted and Clustered

Compare heap, sorted and clustered file organizations with an I/O cost model, learn row vs column layout, and see rowid vs WITHOUT ROWID tables in SQLite.

A table is a logical idea. On disk it is a file made of pages, and the DBMS must decide in what order the records are placed inside those pages. That decision is the file organization. It does not change what a query returns, but it changes how many pages the engine has to read and write to find a row, to scan a range, or to add a new record.

Because disk reads dominate the cost of a query, database courses count cost in page I/Os instead of seconds or CPU instructions. In this lesson you will build a small cost model, apply it to three classic organizations (heap, sorted and clustered), and then look at how SQLite exposes the same choice through ordinary tables and WITHOUT ROWID tables.

Three ways to lay out a file

Heap Records go wherever there is room.
Sorted Records stay ordered by a search key.
Clustered A tree keeps the data pages in key order.

Same rows, very different I/O bills.

1 / 2

The cost model

Assume the file holds R records, each page fits B records, so the file has P = ceil(R / B) data pages. We count one I/O per page read or written, and we ask the same five questions about each organization:

  1. Full scan: read every record.
  2. Equality search: find the record whose key equals a value (unique key).
  3. Range search: find all records with a key between two values.
  4. Insert: add one record.
  5. Delete: remove one record that we located by key.

The numbers below are averages and rounded to keep formulas readable. The real engine adds details such as free-space maps and overflow, but the shape of the result is the same.

Heap files

A heap file has no order at all. New records go to any page with free space, usually the last one. A heap is the cheapest structure to fill and the most expensive to search.

  • Scan: P page reads.
  • Equality search: on average half the file, P / 2, when the value exists; all P pages when it does not, because you can never stop early.
  • Range search: P, since matching records are scattered everywhere.
  • Insert: about 2 I/Os (read the last page, write it back).
  • Delete: the search cost plus 1 write to mark the slot free.

Heaps are a good choice when the table is small, when you almost always read the whole table (loading, reports), or when another structure, an index, does the searching.

Sorted files

A sorted file (sequential file) keeps records ordered by a search key, and the pages are laid out in that order. Now binary search over pages works: compare the key with the middle page, discard half, and repeat.

  • Equality search: about log2(P) page reads.
  • Range search: log2(P) to find the first match, then read the following pages in sequence: log2(P) + m, where m is the number of pages holding matches. Sequential reads are also much faster than random reads on a spinning disk.
  • Insert: the new record must go to its sorted position. Finding it costs log2(P), but making room means shifting later records. On average half the pages are read and written back, about P I/Os. Systems soften this by leaving gaps in pages or by keeping an unsorted overflow area.
  • Delete: search plus rewriting the shifted pages, or marking the slot as deleted and compacting later.

Sorted files make searching on one key fast but pay for it on every insert. They only help for the key they are sorted by: a search on any other column is a full scan again.

Clustered files

A clustered organization stores the records themselves inside a tree, normally a B+ tree, keyed by the clustering key. The data pages are the leaves, and they are kept in key order, yet the tree absorbs inserts by splitting pages instead of shifting the whole file. The word "clustered" also expresses a promise: records with nearby key values are stored on the same or neighbouring pages.

  • Equality search: the height of the tree, usually 3 or 4 reads, regardless of table size.
  • Range search: descend once, then follow leaf links: height + m.
  • Insert: about height + 1 I/Os; occasionally a page splits.
  • Delete: about height + 1.

A table can be clustered by only one key, because the rows can be physically in only one order. Other searches use secondary indexes (see Indexing Basics).

Putting numbers on it

The next TryIt applies the formulas to a file of 1,000,000 records with 50 records per page (so P = 20,000 pages) and a tree height of 3. Change R, B or H and run it again to see how the gap grows.

Python I/O cost model for three file organizations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the table column by column. The heap wins on inserts, loses on every search. The sorted file turns equality search into 15 reads but pays about 20,000 I/Os per insert. The clustered file is never the worst and is the best or tied almost everywhere, which is why practically every production engine builds its main table structure on a tree.

Row layout and column layout

Inside a page the records are normally stored row by row (an N-ary storage model): all columns of one row sit next to each other. That is ideal for transactional work such as "load order 42 with all its fields".

A column store keeps each column in its own run of pages. A query such as SELECT avg(price) FROM sales then reads only the price pages, and the repeated values of a single column compress very well. The price is that rebuilding a whole row touches many places. You will meet this in OLTP vs OLAP. SQLite, like most OLTP engines, is a row store.

Rowid tables and WITHOUT ROWID in SQLite

SQLite gives you both a heap-like and a clustered choice in plain SQL.

  • An ordinary table is stored in a B-tree keyed by a hidden integer, the rowid. The rows are in rowid order, so a lookup by INTEGER PRIMARY KEY (which is just an alias for the rowid) is a tree descent. Any other primary key is a separate unique index, so the table is not clustered by it.
  • A WITHOUT ROWID table is stored in a B-tree keyed by the declared primary key. The table is the index: this is a clustered organization.

The first TryIt builds a thousand-row table and asks SQLite for its plan with EXPLAIN QUERY PLAN, which shows how it will search without running the query. SEARCH means a tree descent, SCAN means looking at every row.

SQL SEARCH or SCAN? Reading plans on a rowid table

Press Run (or Ctrl + Enter) to see the result here.

The three plans read SEARCH products USING INTEGER PRIMARY KEY (rowid=?), SCAN products and SEARCH products USING INTEGER PRIMARY KEY (rowid>? AND rowid<?). The sku query is the "heap" case: the clustering key is the rowid, so no other column can use it.

Now the same data twice: once as a normal table with a text primary key, once as WITHOUT ROWID.

SQL Rowid table vs WITHOUT ROWID table

Press Run (or Ctrl + Enter) to see the result here.

The plans differ in one detail: plain uses INDEX sqlite_autoindex_plain_1, the hidden second B-tree that maps sku to the rowid, followed by a second lookup in the table; clustered finds the row in a single descent with USING PRIMARY KEY. That is why WITHOUT ROWID tables are smaller (one tree instead of two) and a little faster for key lookups. Loading 5,000 rows like these into a fresh database each, the plain table occupied 71 pages of 4 KB while the WITHOUT ROWID table needed 48. The trade-off: wide rows in a WITHOUT ROWID table make the tree's inner pages hold fewer keys, so it is best for rows that are short and keyed by a non-integer key.

What runs live here: SQLite's two table layouts and its query plans. Heap files, sorted files and clustered files in other engines (for example InnoDB's clustered primary key, or PostgreSQL's heap plus CLUSTER command) are explained in text only.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A heap file has 10,000 pages. About how many page reads does an equality search on a unique key need on average, when the key exists?

    A heap has no order, so you scan until you find the record. On average that is half the file. Only a search for a missing key reads all pages.
  2. 2. Why is inserting into a sorted file expensive?

    Finding the position is cheap (log2 of the page count), but making room moves on average half of the file.
  3. 3. How many clustered organizations can one table have?

    The data pages follow a single key order. Other access paths are secondary indexes that point to the rows.
  4. 4. In SQLite, what is special about a WITHOUT ROWID table?

    A normal table is keyed by the hidden rowid and needs a separate index for any other key. A WITHOUT ROWID table is clustered on its primary key.
  5. 5. Which workload fits a column store best?

    Reading one column means reading only that column's pages, and the values compress well. Row-at-a-time work favors a row store.

Summary

  • File organization decides how records are placed in pages; cost is measured in page I/Os.
  • A heap is cheap to insert into and slow to search; a sorted file searches in log2(P) but pays heavily for inserts; a clustered tree balances both with a cost of about the tree height.
  • A table can be clustered on only one key; other searches need secondary indexes.
  • Row stores keep whole records together (good for OLTP); column stores keep each column together (good for analytics).
  • SQLite rowid tables are keyed by the hidden rowid; WITHOUT ROWID tables are clustered on the declared primary key. EXPLAIN QUERY PLAN shows SEARCH vs SCAN.

Next: Indexing Basics: Dense, Sparse, Primary and Secondary.