Skip to content
Tutorials Center
My learning

Topics

Lesson 53 of 79 ยท Storage and Indexing

Multilevel Indexing and ISAM

Learn how ISAM builds a static multilevel index over sorted pages, why overflow chains slow it down and how it differs from a B+ tree, with a live simulation.

A single index over a big file is itself a big file, and searching it costs many page reads. Indexing Basics showed the cure: index the index, again and again, until the top level fits on one page. That layered design is a multilevel index, and one of the oldest practical versions of it is ISAM, the Indexed Sequential Access Method. IBM introduced it for mainframe files in the 1960s, and its ideas still appear in embedded stores and in the way some systems lay out read-mostly data.

ISAM is worth studying even if you will mostly use B+ trees. It is the simplest structure that gives you logarithmic lookups, and its one big weakness, that the shape never changes after it is built, explains exactly why the B-tree family was invented.

Anatomy of an ISAM file

ISAM works on a data file that is sorted by the search key and stored in consecutive pages. On top of it you build levels of sparse index:

  1. Leaf (data) pages. The records, sorted by key. When the file is built each page is left partly empty on purpose, to absorb a few later inserts.
  2. Bottom index level. One entry per data page: the smallest key on that page and a pointer to the page. Entries are packed into index pages.
  3. Higher index levels. One entry per page of the level below, again (smallest key, pointer). Repeat until a single page, the root, is left.
  4. Overflow pages. Created later when an insert finds its data page full. They hang off the data page as a linked chain.
flowchart TD
  R["root index page"] --> I1["index page A"]
  R --> I2["index page B"]
  I1 --> D1["data page 1"]
  I1 --> D2["data page 2"]
  I2 --> D3["data page 3"]
  I2 --> D4["data page 4"]
  D2 --> O1["overflow page"]
  O1 --> O2["overflow page"]

The index levels (top) never change. Overflow pages (bottom right) are bolted on afterwards.

The key property is that the index is static. All the index pages are built in one pass, written once and then only read. Inserts and deletes touch data and overflow pages only. This is what makes ISAM simple and fast to read: no locks on the upper levels, no splits, no rebalancing.

Searching

A lookup walks from the root down, reading exactly one page per level. In each index page you pick the last entry whose key is less than or equal to the search key and follow its pointer. At the bottom you land on a data page and scan it, then follow its overflow chain if it has one.

The cost is the number of index levels plus one data page plus the length of any overflow chain. With a fan-out of F entries per index page and P data pages, the number of levels is about ceil(log_F(P)). With a realistic fan-out of a few hundred, three index levels cover tens of millions of data pages.

Building and probing an ISAM file

The simulation below builds an ISAM structure over 60 keys (10, 20, ..., 600). Each data page holds up to 4 records but is built with only 3 (the free slot is the room for growth), and each index page holds up to 4 entries. It counts page reads the way a real engine would.

Python A static ISAM index in Python

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.

Look at the results. A search in the original file costs 4 page reads: three index levels and one data page. After the hot-spot inserts, the two data pages around keys 301 to 321 have grown overflow chains. Searching for 305 now costs 5 reads and searching for 321 costs 7, one extra page per link, while the index levels stay exactly as they were. Spread-out inserts, on the other hand, mostly fit into the free slots that were left on purpose, and chains stay short.

Why ISAM degrades

Overflow pages are the price of a static index. ISAM has no way to split a full page, because splitting would change the number of data pages and invalidate the index that points to them. So:

  • Skewed inserts create long chains. If new keys keep arriving in one range (ever-increasing order numbers, a popular customer), one chain grows and every search in that range gets slower, up to a sequential scan of the chain.
  • Overflow pages are not sorted into the file. They live wherever the engine found free space, so range scans jump around the disk.
  • Deletes leave holes. Removing records frees space inside pages, but the empty space is only reused by later inserts into the same range. Pages never merge.
  • The cure is a rebuild. A DBA reorganizes the file: read everything in key order, write fresh pages and rebuild the index. During that time the file is usually unavailable or read-only.

On the positive side, ISAM has real strengths. Because the index never changes, readers do not need to lock index pages at all, and a lookup is predictable. Locking is needed only on data and overflow pages, which raises concurrency.

ISAM compared with the B+ tree

Question ISAM B+ tree
Index levels after build fixed forever grow and shrink with the data
What happens when a page is full overflow chain page splits, parent updated
Behavior under many inserts degrades until rebuilt stays balanced automatically
Locking the index not needed (read-only) needed (splits change it)
Best workload mostly static, read-heavy data general purpose
Maintenance periodic reorganization none

A B+ tree is, in effect, ISAM with the missing piece added: when a page overflows, split it and add an entry to the parent, which may split in turn all the way to the root, keeping every leaf at the same depth. You pay a little on inserts and gain stable lookups forever. That is why almost every modern engine uses B+ trees, while ISAM survives in static data sets, read-only files and as a teaching model.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does it mean that an ISAM index is static?

    Inserts and deletes touch only data and overflow pages. The index levels keep the shape they were given at build time.
  2. 2. An ISAM data page is full and a new record belongs on it. What happens?

    Splitting would change the number of data pages that the static index points to, so ISAM chains an overflow page instead.
  3. 3. With 4 index levels, how many page reads does a successful lookup need if the target data page has no overflow chain?

    One read per index level plus one for the data page: 4 + 1 = 5.
  4. 4. Which workload suits ISAM best?

    Static data keeps overflow chains short and lets readers skip index locking. Hot-spot inserts are the worst case.
  5. 5. What is the main fix that B+ trees add to the ISAM idea?

    Page splits that propagate upward keep all leaves at the same depth, so lookup cost stays stable without reorganizing.

Summary

  • A multilevel index is an index on an index, repeated until one root page remains. A lookup reads one page per level, plus the data page.
  • ISAM builds a static multilevel sparse index over a sorted file and leaves free slots in data pages for growth.
  • Full pages get overflow chains, so ISAM degrades under skewed inserts and needs periodic reorganization.
  • Its static index means no index locking and very predictable reads for static data.
  • B+ trees fix its weakness by splitting pages and keeping every leaf at the same depth.

Next, continue with B-Trees and B+ Trees to see the self-balancing version in detail.