Balanced Search Trees and B-Trees
Balanced search trees maintain useful height bounds as keys change. Page-oriented B-trees group multiple keys and child references to match a storage-oriented access model. Both support ordered search, but the relevant costs include comparisons, memory access, page access and maintenance under writes.
Begin with the operations the workload needs: exact lookup, predecessor/successor, range scan, insertion or deletion. Then identify whether the important boundary is an in-memory object structure or a database index. A logarithmic label alone does not tell you how many storage reads or milliseconds a query will require.
TL;DR
- Balanced search trees keep height logarithmic as keys change, so ordered operations stay predictable.
- B-trees pack many keys and child pointers into each page to match storage access, which is why databases use them for indexes.
- Start from the operations you need: exact lookup, predecessor and successor, range scans, inserts, and deletes.
- Real cost includes comparisons, memory and page accesses, and write maintenance; "O(log n)" alone does not predict milliseconds or disk reads.
- An index existing doesn't mean the planner will use it — check the plan for the complete query.
Quick Example
This Python example uses an in-memory SQLite database. It checks a range result and confirms that the observed plan names the created index. It does not implement a B-tree or inspect its balancing procedure.
The query returns 497, 498 and 499 in order. The plan assertion confirms index involvement for this schema, query and runtime. It does not measure page reads, insertion cost, disk persistence or PostgreSQL behavior. A different query or distribution can justify another plan, so avoid interpreting this one result as a universal optimizer rule.
Core Concepts
Ordering and balance are separate invariants
A binary search tree's ordering rule determines which subtree can contain a key. A balance rule keeps the height from growing like a long chain under unfavorable update order. A tree can remain correctly ordered while becoming expensive to search if it lacks the needed height control.
MIT's AVL notes describe height balance and rotations as a way to preserve logarithmic-height operations under the specified structure. That is a concrete balanced binary-tree design, not a claim that every structure with tree in its name has identical update rules. MIT AVL notes
When implementing such a structure, test ordering, stored metadata and balance after updates. A lookup test alone can pass while a height field is wrong or a later rotation fails. Compare ordered traversal and predecessor/successor behavior against a simple reference where practical.
A database page changes the cost model
SQLite's file-format documentation describes interior and leaf B-tree pages, keys and child pointers. The page groups several logical entries, so traversing one child link is different from following one pointer per key in a basic binary tree. SQLite B-tree format
Think in terms of the actual page layout, key size, occupancy and cache behavior. More keys per page can reduce the number of page levels, while large keys or payloads change capacity and overflow behavior. Those mechanisms motivate measurement; they do not establish a page count for the tiny fixture.
This table is an editorial comparison of mechanisms. It gives no measured winner and does not make the SQLite index a test of every listed structure.
Query shape determines index usefulness
PostgreSQL documents B-tree support for ordered equality and range conditions and notes that retrieving sorted output through an index is not always faster than scanning and sorting. The planner's choice depends on the actual query and data. PostgreSQL index types
Review composite keys, ordering, selected columns and expected result size together. An index that helps a narrow range can be less useful for a large fraction of the table. A covering access path can avoid some row lookups, but that needs evidence from the chosen database and plan rather than an assumption based on the index name.
Writes pay for maintained access paths
An index must remain consistent as rows change. Evaluate storage, insert/update/delete overhead, concurrency and maintenance in the actual database. A useful read improvement can still be the right choice, but its write cost belongs in the decision.
Do not infer update cost from a read-only plan check. The fixture inserts before creating the index and then inspects a read. It does not compare indexed and unindexed write workloads, observe splits or measure lock behavior.
Best Practices
Choose a cost model and name its unit. For algorithm analysis, count comparisons or structural steps under stated assumptions. For a storage-backed workload, inspect page and cache behavior and measure representative latency. Keep those claims distinct even when both are relevant to the same system.
Use representative keys and operations. Sorted insertion, repeated keys, variable-sized values, range width and update mix can expose different behavior. A test with a thousand consecutive integers is a useful controlled case but does not represent every production distribution.
When testing a database index, preserve schema, query, parameters, statistics context and runtime version. Verify result correctness before comparing plans or time. A plan change that returns different semantics is not a valid performance comparison.
When implementing a balanced tree, check invariants after sequences of insertions and deletions, including root replacement and empty transitions. Use a simple sorted reference for contents and ordering. The article's SQLite fixture does not implement or validate these internal algorithms.
Reverse an index recommendation when representative evidence shows broad scans or write overhead dominate its benefit. Choose an ordered tree when ordered operations matter; choose another structure when its actual semantics better fit the task. The name of a data structure should summarize the mechanism, not end the analysis.
Common Mistakes
Calling any binary search tree balanced
Treating logarithmic height as a latency promise
Assuming an index will be used
Generalizing one database's plan to another
FAQ
Is a B-tree just a binary search tree on disk?
No. A page-oriented B-tree groups multiple keys and child relationships, with layout and maintenance designed for its access model. Review the actual implementation rather than mapping one binary node directly to a page.
Did the example measure index speed?
No. It verified the range result and index name in the observed SQLite plan. It supplies no latency, page-IO or write-cost benchmark.
Should every searchable column have an index?
Evaluate the query benefit against maintenance, storage and workload costs. An index is a maintained access path, not free metadata.