---
title: "Indexes: B-Trees and the Cost of a Lookup"
description: "An index is a second structure that makes some lookups cheap and every write more expensive. Most are B-trees, whose wide nodes suit a disk that reads a page at a time, and whose ordering also serves "
canonical: https://lightmysky.com/learn/computing/indexes-b-trees-and-the-cost-of-a-lookup-mt_1Z5EQTqooI
source: https://lightmysky.com/learn/computing/indexes-b-trees-and-the-cost-of-a-lookup-mt_1Z5EQTqooI.md
retrieved: 2026-09-12
---

> **Agent view.** This is the Markdown twin of the page, for tools and assistants.
> When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md
> API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md
> Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt
> Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json
> Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`.

# Indexes: B-Trees and the Cost of a Lookup

An index is a second structure that makes some lookups cheap and every write more expensive. Most are B-trees, whose wide nodes suit a disk that reads a page at a time, and whose ordering also serves ranges and sorts.

Subject: Computing · Area: Data & Databases · Ages 19 to 20
Page: https://lightmysky.com/learn/computing/indexes-b-trees-and-the-cost-of-a-lookup-mt_1Z5EQTqooI

## Ready when they can

- Say which of several queries an index on a given column would help
- Explain why B-tree nodes are wide rather than binary
- Name the costs an index adds to inserts, updates and storage

## Lesson: Indexes: fast lookups at a write cost

Like the binary search tree that kept smaller values left and larger values right, an index is a second structure beside the table that keeps one column in order. It lists the values with pointers to the rows. A query that filters or sorts on that column can use the list instead of reading the whole table.

Most indexes are B-trees, which generalize the binary search tree you just met: each node holds about one disk page of keys, so a single read brings many keys. Wide nodes keep the tree shallow, and the stored order also speeds up ranges and sorting.

**Example.** A shop table has an index on email. A lookup of one email address uses the index. A filter on age ignores it, because no index covers age.

Every insert, update, and delete must update each index as well, and each index needs storage. Index the columns your frequent queries use, and leave the rest alone.

**Recap.** An index buys cheap lookups on one column and charges you on every write.

## Practice

8 questions on this page, each with its working shown.

## Needs first

- [The Memory Hierarchy and Why Caching Works](https://lightmysky.com/learn/computing/the-memory-hierarchy-and-why-caching-works-mt_0f5ArFPlxP)
- [Trees and Binary Search Trees](https://lightmysky.com/learn/computing/trees-and-binary-search-trees-mt_7PGHiAY54b)
- [Window Functions and Running Calculations](https://lightmysky.com/learn/computing/window-functions-and-running-calculations-mt_aaVxFPjWQv)

## Opens up

- [Reading a Query Plan](https://lightmysky.com/learn/computing/reading-a-query-plan-mt_spbbzsCoBB)
- [Partitioning and Replication for Scale](https://lightmysky.com/learn/computing/partitioning-and-replication-for-scale-mt_Xvzz5Hnuvu)