MySmartCoPilot
Ask Passes Your pass 7 days left 1 day left Last day

Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

Data Structures & Algorithms (DSA)  Module 21 – Algorithms in practice

Data structures inside real software

The B-trees of SQLite and PostgreSQL, the red-black tree of the Linux scheduler, the hash maps of Python, Java and Go, and the graphs of build tools.

  • Intermediate
  • 25 minutes
  • Examples run with Python 3.14.8, Pyodide 314.0.7, Node.js 24.21.0 and quickjs 0.32.0
  • By MySmartCoPilot
Free: Documented choices, and what decides them · Reading the documentation for the structure · Check yourself. With a pass: 2 in-depth parts and 3 interview answers, about 15 minutes.

What you will learn

  • Find the data structures that databases, schedulers and runtimes document using
  • Connect each choice to its trade-off
  • Read technical documentation to discover such choices

Before you start

What you’ll learn · Before you start

What you will learn

  • Find the data structures that databases, schedulers and runtimes document using
  • Connect each choice to its trade-off
  • Read technical documentation to discover such choices

Before you start

On this page

The data structures of a textbook are the ones real software runs on, and its documentation usually says which. SQLite stores every table and index as a B-tree of pages, and PostgreSQL builds B-tree indexes unless asked for another kind. The Linux kernel’s CFS scheduler keeps runnable tasks in a red-black tree ordered by how much processor time they have had. Java’s TreeMap is a red-black tree and its HashMap a hash table; Python’s dict is a hash table that keeps insertion order, and Go leaves the order of its maps unspecified. Build tools and package managers order work as a directed acyclic graph. Each choice follows from the operations the system performs most often, and this lesson shows how to read it off the documentation, then opens a real database file to check.

Documented choices, and what decides them

  • SQLite stores every table and index as a B-tree of fixed-size pages in one file, for lookups by key and ordered ranges in a few page reads each.
  • PostgreSQL’s CREATE INDEX builds a B-tree by default, for equality and range comparisons; Hash, GiST, SP-GiST, GIN and BRIN indexes serve other kinds of query.
  • Linux CFS keeps runnable tasks in a time-ordered red-black tree and runs the leftmost, because a scheduler takes the smallest, inserts, and removes any task.
  • Java’s TreeMap is a red-black tree with log(n) get, put and remove, for sorted keys with floor and ceiling queries.
  • Java’s HashMap is a hash table with constant-time get and put and no promise about order: exact lookups only.
  • Python’s dict is a hash table that iterates in insertion order: exact lookups and a predictable order of keys.
  • Go maps are hash tables whose iteration order is unspecified: exact lookups, with any order left to the programmer.
  • Python’s graphlib and build tools produce a topological order of a dependency graph, or an error naming a cycle, so that every task runs after the tasks it needs.

The pattern repeats. B-trees win where data lives on disk in pages and ordered ranges matter: one page holds a hundred keys or more, so a search reads a handful of pages. Balanced binary trees such as red-black trees win in memory when the program needs the smallest item, insertions and removals of any item, and sorted iteration, each in O(log n). Hash tables win when only exact lookups matter, at the price of any order. PostgreSQL’s other index types each serve another kind of query: Hash only equality, GiST and SP-GiST geometry and other custom searches, GIN the words inside a text, and BRIN huge tables stored in time order. Graphs model dependencies, and a topological order is the schedule. SQLite’s documentation describes its file like this:

An SQLite file as pages: page 1 holds the header and the schema, which points to each B-tree of root, interior and leaf pages.One database file:pages of one size, numbered from 1Page 1: the 100-byte file header,then the root of sqlite_schema,which lists the root page of every table and indexRoot page of a table or an indexInterior pages:keys and child page numbersLeaf pages: the rows (table)or the keys (index), in key orderroot page numberchild pointerschild pointers

How an SQLite database file stores its tables and indexes

Text description of the diagram

The diagram is a column of five boxes joined by arrows from top to bottom.

  1. One database file, made of pages of one size, numbered from 1.
  2. Page 1 starts with the 100-byte file header and then holds the root of the sqlite_schema table, which lists the root page of every table and index.
  3. An arrow labelled "root page number" leads to the root page of a table or an index.
  4. Arrows labelled "child pointers" lead to interior pages, which hold keys and the page numbers of their children.
  5. More child pointers lead to the leaf pages, which hold the rows of a table, or the keys of an index, in key order.
SQLite Viewer & Editor Open any SQLite database file in the browser and browse its tables and indexes.

Reading the documentation for the structure

The structure behind a feature is rarely a secret, but it is spread over different kinds of documents:

  • File-format and internals pages describe the layout itself: SQLite’s “Database File Format” names the B-tree page types byte by byte.
  • API documentation states guarantees that only some structures can keep: “guaranteed log(n) time” and sorted keys point to a balanced tree, “no guarantees as to the order” points to a hash table.
  • Language specifications fix observable behaviour: insertion order for a Python dict or a JavaScript Map, and an unspecified order for a Go map.
  • Experiments confirm what the documents say, as the rest of this lesson does.

Python’s own standard library shows the dependency case. graphlib.TopologicalSorter takes each node with the nodes it needs and returns an order in which every node comes after its needs; if the needs form a cycle, it raises CycleError and names the cycle:

An install order for nine packages, and a cycle Python · core/build_order.py 
# A package manager installs every dependency before the packages that need it: a topological order of the
# dependency graph. graphlib, in the standard library, computes one and names a cycle when there is one.
from graphlib import CycleError, TopologicalSorter

requires = {  # package: the packages it needs (tuples keep the order of the output the same on every run)
    "webapp": ("framework", "orm", "templates"),
    "framework": ("http", "routing"),
    "orm": ("db-driver", "pool"),
    "templates": ("markup",),
    "routing": ("http",),
    "db-driver": (),
    "http": (),
    "pool": (),
    "markup": (),
}
order = list(TopologicalSorter(requires).static_order())
print("install order:", ", ".join(order))
position = {package: i for i, package in enumerate(order)}
print("every package after what it needs:", all(position[d] < position[p] for p, needs in requires.items() for d in needs))

requires["http"] = ("webapp",)  # a mistake: http now needs webapp, which needs http through framework
try:
    TopologicalSorter(requires).prepare()
except CycleError as error:
    cycle = error.args[1]  # each package in it is needed by the next one
    print("cycle found:", " needs ".join(reversed(cycle)))

Output

install order: http, db-driver, pool, markup, routing, orm, templates, framework, webapp
every package after what it needs: True
cycle found: webapp needs framework needs http needs webapp

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 build_order.py

The order installs http before routing, framework and webapp, and the check confirms every package comes after everything it needs. Once http was made to need webapp, no order could exist, and the error named the loop, the same report a package manager gives for circular dependencies.

Check yourself

Check yourself

8 questions about this lesson. Every answer and why it is right is on the page, behind “Show the answer”. Your score stays in this browser.

  1. Question 1 of 8 According to SQLite's file-format documentation, how is every table and index stored in the database file?

    Choose one answer.

    Show the answer

    Answer: As a B-tree of fixed-size pages

    The file is a sequence of pages of one size, and each table and each index is a B-tree of those pages; page 1 holds the schema table, which records the root page of every other B-tree. Source: "Database File Format" on sqlite.org.

  2. Question 2 of 8 Which index type does PostgreSQL's CREATE INDEX build when no type is named?

    Choose one answer.

    Show the answer

    Answer: B-tree

    PostgreSQL's documentation on index types says CREATE INDEX creates B-tree indexes by default, because they fit the most common situations: equality and range comparisons on data that can be sorted. Source: "Index Types" in the PostgreSQL documentation.

  3. Question 3 of 8 Which task does the Linux CFS scheduler pick next, according to the kernel's documentation?

    Choose one answer.

    Show the answer

    Answer: The leftmost task of a red-black tree ordered by virtual runtime

    CFS keeps runnable tasks in a time-ordered red-black tree sorted by their virtual runtime and runs the leftmost one, the task that has had the least virtual time so far. Source: "CFS Scheduler" in the Linux kernel documentation.

  4. Question 4 of 8 Java's TreeMap guarantees log(n) time for get, put, remove and containsKey. Which structure does its documentation name?

    Choose one answer.

    Show the answer

    Answer: A red-black tree

    The class description of java.util.TreeMap begins "A Red-Black tree based NavigableMap implementation" and states the log(n) guarantees. Its sibling HashMap is a hash table that makes no promise about order.

  5. Question 5 of 8 Which of these iteration orders does the language's own documentation or standard guarantee?

    Choose every answer that is right.

    Show the answer

    Answer:

    • A JavaScript Map iterates in insertion order
    • A Python dict iterates in insertion order

    Python guarantees insertion order for dicts from version 3.7, and the ECMAScript standard defines a Map's iteration in key insertion order. Go's specification gives map iteration no fixed order, and Java's HashMap promises no order either.

  6. Question 6 of 8 What does graphlib's TopologicalSorter do when the dependency graph has a cycle?

    Choose one answer.

    Show the answer

    Answer: It raises CycleError, and the exception names the cycle it found

    prepare(), which static_order() calls, checks the graph and raises CycleError; the second element of the exception's args is a list of the nodes on the cycle, with the first node repeated at the end.

  7. Question 7 of 8 Java documents PriorityQueue as "based on a priority heap". Which of its operations does the documentation say takes linear time?

    Choose one answer.

    Show the answer

    Answer: remove(Object), which removes a particular element

    Its implementation note gives O(log n) for offer, poll, remove() and add, constant time for peek, element and size, and linear time for remove(Object) and contains(Object): a heap keeps no index of where an element is, so it must search for it. A scheduler that often removes arbitrary tasks pays exactly that cost.

  8. Question 8 of 8 Which PostgreSQL index type does the text-search documentation call the preferred index for full-text search?

    Choose one answer.

    Show the answer

    Answer: GIN, an inverted index with an entry for each word

    The documentation calls GIN indexes the preferred text-search index type: as inverted indexes, they hold an entry for each word (lexeme) with a compressed list of matching locations. A B-tree or hash index over the whole text can only find texts that are equal, not texts that contain a word.

GATE CS

The GATE 2027 syllabus for Computer Science and Information Technology lists “File organization, indexing (e.g., B and B+ trees)” under Databases, and “CPU and I/O scheduling” under Operating System, so the B-trees of a database file and the ordered tree of a scheduler both belong to the exam as well as to practice.

Inside an SQLite file: B-tree pages, byte by byte Pro

SQLite’s documentation describes its file down to the byte. This part builds a database of 200,000 rows, reads the page types and fill of both of its B-trees directly from the file, and turns the measured densities into the depth of a billion-row table.

In this part:

  • Reading the page types of a real database file, measured
  • Why a B-tree beats a binary tree on disk, in numbers
  • Index types beyond the B-tree, and the queries each one serves

1 runnable example (Python) · about 3 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

  • Pro pass · 1 week₹79$2.99
  • 30 days₹179$5.99
  • 1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a passI have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Schedulers, maps and build graphs: choices you can observe Pro

The other structures of the table show up in behaviour you can reproduce. This part simulates the scheduler’s ordered tree and the failure it is designed to avoid, prints the iteration orders that the standards fix, and schedules a build on several workers.

In this part:

  • A scheduler’s ordered tree, simulated, and the failure it avoids
  • Why an ordered tree and not a heap: the operations, compared
  • Map order you can observe, and the bugs it causes
  • Build graphs: parallel rounds and the critical path, worked

3 runnable examples (JavaScript, Python) · about 4 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

  • Pro pass · 1 week₹79$2.99
  • 30 days₹179$5.99
  • 1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a passI have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Interview questions

  1. Fresher to mid · Warm-up

    Why do databases store tables and indexes as B-trees rather than as binary search trees or hash tables?

    A database reads its data from disk in pages of a few kilobytes, so what counts is the number of pages a search touches. A B-tree packs a hundred or more keys into each page, so even a billion rows sit only four or five levels deep, and the top levels stay in memory; a binary search tree over the same rows is about 30 levels deep, which could mean 30 separate reads. A hash index finds an exact key in about one read but keeps no order, so it cannot answer ranges, sorting or "the next key after x", which a B-tree answers by reading neighbouring leaf pages. SQLite stores every table and index as a B-tree, and PostgreSQL builds B-tree indexes by default.

  2. Mid to senior

    A PostgreSQL table holds 300 million orders. Queries look orders up by customer, report on date ranges of the last few days, and search the free-text delivery notes for words. Which index would you build for each query, and what does each cost?

    First step and follow-ups

  3. Mid to senior

    A Python service builds a JSON response by iterating over a dict, and a client parses the fields by position. After the service is rewritten in Go, the client breaks on some requests but not others. Explain why, and how you would fix it on both sides.

    First step and follow-ups

  4. Senior to staff

    The Linux CFS scheduler kept runnable tasks in a red-black tree ordered by virtual runtime. A colleague says a binary heap would be simpler and just as fast. Compare the two for the scheduler's operations, and say what you would choose.

    First step and follow-ups

Key takeaways

  • Real software documents its data structures: SQLite’s file format, PostgreSQL’s index types, the kernel’s scheduler notes, and the API documentation of Java, Python and Go.
  • B-trees serve ordered data on disk in few page reads; red-black trees serve the smallest item, insertions, removals and sorted iteration in memory; hash tables serve exact lookups without order; graphs serve dependencies.
  • Guarantees in documentation point to structures: log(n) bounds and sorted keys to balanced trees, “no order” to hash tables.
  • Never rely on an order a structure does not promise: Python’s dict and JavaScript’s Map keep insertion order, Go maps and Java’s HashMap do not.

References

Related tools

SQLite Viewer & Editor Look inside any SQLite database and change it; with a pass, download the result. Hex Viewer & File Inspector A private hex viewer for files of any size, with a data inspector and file-type detection.

Report a problem with this lesson