Tree or B-Tree Index¶
Ordered index structure — instantiates Operation-Weighted Data Structure Design
Keeps keys in sorted, balanced order so point lookups and range scans both run in logarithmic time, with node fanout sized to the storage block.
A Tree or B-Tree Index stores keys in sorted, balanced order, and that single commitment is what sets it apart from its nearest sibling, the hash table: because the keys are ordered, it answers not just "find this key" but "find everything between here and there" and "walk in order" cheaply — queries a hash cannot serve at all. The balance invariant keeps the worst-case height logarithmic, and the B-tree variant sizes each node to fill one storage block so the tree stays shallow and a lookup costs only a handful of block reads. It buys ordered, range-friendly access by giving up a little raw point-lookup speed and paying to rebalance on every write.
Example¶
A public library catalog is indexed by call number. Patrons look up an exact call number (a point query), but they also browse "everything between 512.3 and 513.9" (a range) and want results in shelf order (ordered traversal). A hash index would nail the exact lookup and be useless for the other two — hashing deliberately scatters neighboring keys. A B-tree on call number instead keeps entries sorted, with fanout chosen so each node fills a storage page; even a catalog of several million items sits only three or four levels deep, so any lookup is a few block reads, and a range query becomes "descend to the start, then walk the linked leaves." The browse-by-range access pattern is served for free by the ordering the tree already maintains.
How it works¶
- Sorted keys, high fanout. Keys are held in order across nodes; each node packs many keys so the tree is broad and shallow rather than tall.
- Node = block. Node size is matched to the storage page or cache line, so descending one level costs one read.
- Balance on mutation. Inserts and deletes split and merge nodes to preserve the height invariant, so worst-case cost never degrades.
- Linked leaves for ranges. In the B+-tree form, leaves are chained so a range scan is a sequential walk, not repeated root-to-leaf descents.
What distinguishes it from every other structure here is the maintained ordering-plus-balance invariant — that is the property that makes range and ordered access cheap.
Tuning parameters¶
- Node size / fanout — matched to page or cache-line size. Bigger nodes give a shorter tree and fewer I/Os but costlier in-node search and rewrites.
- Fill factor — how full nodes are packed. Dense packing saves space and reads but makes inserts split more often (write amplification).
- B-tree vs B+-tree vs plain BST — whether values live in internal nodes or only in linked leaves, and whether the tree lives on disk or in memory.
- Clustered vs secondary — whether the tree defines the physical row order or merely points at rows stored elsewhere.
- Key and composite order — which column(s), and in what order, since that fixes exactly which ranges are cheap and which are not.
When it helps, and when it misleads¶
Its strength is being the workhorse when a workload needs both point and range/ordered access and the data is too big to keep in memory: predictable logarithmic worst case, and sequential leaf scans that are kind to cache and disk. It misleads when the workload is pure point-lookup with no range need at all — there a hash table is faster and simpler, and a tree is over-engineering — and it taxes write-heavy workloads with constant rebalancing. The classic misuse is reaching for the familiar B-tree by reflex, then justifying it, when the trace shows no range queries whatsoever. The discipline is to pick the index from the measured access pattern rather than habit, and to remember that the B-tree's whole trick is fanout matched to the storage block.[n1]
How it implements the components¶
structural_invariant_set— the sorted-order and balanced-height invariants it re-establishes on every insert and delete are its defining constraint set; those guarantees are what buy ordered access.space_time_budget— fanout and fill factor are the concrete dials that spend storage to buy fewer block reads, turning an abstract space-versus-time budget into node geometry.
A tree serves an access pattern but does not discover it: the operation_mix_profile and access_pattern_map that tell you a range query even matters come from Workload Benchmark and Trace, and the explicit cost_tradeoff_model weighing this index against redundant read copies belongs to Normalized / Denormalized Schema Pair.
Related¶
- Instantiates: Operation-Weighted Data Structure Design — it is the structure of choice when the weighted operation mix includes ordered and range access.
- Consumes: Workload Benchmark and Trace — the access-pattern map that tells the index which key order and ranges to optimize for.
- Sibling mechanisms: Hash Table or Key-Value Store · Workload Benchmark and Trace · Columnar or Row Layout · Adjacency List or Matrix · Normalized / Denormalized Schema Pair · Materialized View or Cache
Editorial Notes¶
Form Classification¶
Form family: Structure, Architecture & Configuration
Rationale: Tree or B-Tree Index operates as a configured physical, technical, or logical arrangement whose structure creates the effect because it keeps keys in sorted, balanced order so point lookups and range scans both run in logarithmic time, with node fanout sized to the storage block.
Independent corroboration: The frozen evidence defines Tree or B-Tree Index as 'Keeps keys in sorted, balanced order so point lookups and range scans both run in logarithmic time, with node fanout sized to the storage block', so its operative form is Structure, Architecture & Configuration.
Nearest alternative: Representation, Specification & Plan — Tree or B-Tree Index includes features of a static representation, map, specification, schema, or prospective plan that externalizes information, but its defining operation is a configured physical, technical, or logical arrangement whose structure creates the effect.
Review outcome: Independent reviewer agreement; medium confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Single lineage
Present-day reach: Specialized
Rationale: Both independent reviews identify computer science as the historical home of the operation—Keeps keys in sorted, balanced order so point lookups and range scans both run in logarithmic time, with node fanout sized to the storage block.. The retained alternates document formative adjacent traditions; the reach field, not the origin field, carries later applicability.
Related originating lineages:
- Engineering & Design — Engineering design, reliability, and systems-safety practice supplies a parallel or contributing lineage for the mechanism's defining operation: keeps keys in sorted, balanced order so point lookups and range scans both run in logarithmic time, with node fanout sized to the storage block.
Review resolution: Both blind reviewers independently place the defining operation—Keeps keys in sorted, balanced order so point lookups and range scans both run in logarithmic time, with node fanout sized to the storage block.—in computer science. Their queued differences are secondary: origin_mode_disagreement, domain_reach_disagreement, encyclopedia_synthesis_disagreement. Reviewer A contributes no unique alternate; reviewer B contributes no unique alternate. I preserve the full evidence-supported union of 1 alternate domain(s), without a numeric cap. origin_mode=single_lineage reflects the reviewers' evidence about historical construction, while domain_reach=specialized separately reflects present-day portability. The affirmative encyclopedia-synthesis finding is preserved, and confidence=high uses the more conservative reviewer level.
Encyclopedia synthesis: The exact catalogued form synthesizes established practice rather than reproducing a single standard historical label.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
[n1] A B-tree is a balanced search tree whose nodes are sized to the storage block, so its height — and therefore the number of I/Os per lookup — stays tiny even for very large datasets; introduced by Rudolf Bayer and Edward McCreight. Matching node size to the block is the idea that makes it the standard on-disk index. ↩