Search tools and guides ⌘K
Semicolony ELI5 · comic

Database indexes.

The index at the back of a book, instead of reading every page to find a word.

  1. It’s in here somewhere…
    900pp
    1

    You want every mention of one word in a 900-page book.

  2. page 1… page 2… page 3…
    every page, in order
    2

    Without an index, the only option is to read every page in order — a full table scan.

  3. INDEX apple … 12 queue … 412 zebra … 880 sorted, word → pages
    3

    The back-of-the-book index is a sorted shortcut: the word, then the exact pages.

  4. Page 412. Done.
    queue → 412 412
    4

    Because it’s sorted, you find the word in a handful of steps and jump straight there.

  5. 50 25 75 each step halves what’s left
    5

    A database index is the same trick: even a billion rows are only a few dozen steps apart.

  6. Worth it for the lookups.
    write table + index too extra work, extra space
    6

    It isn’t free — every write also updates the index, and it takes disk space.

Reading every page versus flipping to the index at the back. (Bit needs one word in a thick book.)
Semicolony semicolony.dev/eli5/database-index/comic
← All ELI5 explainers