Why is mathematics important in a database? Because “find this record” is not one operation with one cost. A database containing ten rows can scan them all without drama. A database containing hundreds of millions of rows needs an organised route. Ordering, branching, logarithms and probability help the system decide whether to scan, use an index, combine conditions or avoid reading data it does not need.
A B-tree index is one of the clearest examples. It stores sorted keys in a balanced, multiway tree whose pages point toward narrower ranges. Instead of checking every row, the database can descend a few levels, reach the relevant leaf page and follow references to matching table rows. The method is fast because each decision can discard large parts of the search space.
This article explains the mechanism without pretending that every query becomes fast when an index exists. Indexes occupy storage, slow some writes, require maintenance and help only when their structure matches the query and data. A query planner weighs those trade-offs using estimates rather than slogans.
> Did You Know? A practical database B-tree is usually wide, not shaped like the narrow binary trees drawn in early lessons. One page can hold many keys and child pointers, which keeps the tree shallow.
Quick Navigation
- Why a table scan can be expensive
- The ordered-search idea
- What makes a B-tree balanced
- Branching factor and logarithmic height
- A worked search example
- Insertions, splits and write cost
- Range queries and leaf pages
- Composite and covering indexes
- The query planner and selectivity
- A student simulation
- Guidance and pathways
- Frequently asked questions
Why a Table Scan Can Be Expensive
Imagine a school library database with one million loans. A request asks for all loans with student ID 41729. A sequential scan examines every row and tests the condition. In big-O notation, the work grows on the order of \(n\):
\[ T_{scan}(n)=O(n). \]
This does not mean every scan is slow. Rows may be cached, stored compactly or processed in parallel. A query returning most of the table may sensibly use a scan. Big-O describes growth under a model; it is not a stopwatch reading.
The real cost is often page access
Databases store data in pages or blocks. Reading one page brings many rows at once. Mechanical disks, solid-state storage, memory caches and networked storage have different costs, but random and sequential access patterns still matter.
Counting comparisons alone can therefore mislead. An algorithm using fewer comparisons may touch scattered pages, while a scan reads neighbouring pages efficiently. Database mathematics connects algorithmic complexity with a storage model.
A scan has advantages
A sequential scan is simple, visits every qualifying row and can be efficient when:
- the table is small;
- the query returns a large fraction of rows;
- no suitable index exists;
- rows are already cached;
- parallel scanning is effective;
- index lookups would cause many additional table-page visits.
The question is not “Are indexes good?” It is “Which access path is cheapest for this query under current estimates?”
The Ordered-Search Idea
If values are sorted, binary search repeatedly compares with a middle value and discards half the remaining interval. Its comparison count grows like \(\log_2 n\).
For one million sorted values,
\[ \log_2(1{,}000{,}000)\approx19.93. \]
About 20 yes-or-no decisions can isolate a position in the ideal array model, far fewer than one million comparisons.
Binary search and Big-O complexity develops that mechanism directly. A database B-tree keeps the same broad insight—ordered decisions shrink the search space—but adapts it to page-based storage, changing data and many keys per page.
Why not keep one giant sorted array?
A sorted array supports fast search, but inserting a key near the beginning can require shifting many later entries. Database tables also change while users query them. A tree divides the ordered keys across pages so local splits and structural updates can preserve search order without rewriting the entire index.
Order must be well defined
An index relies on comparison semantics: which key is less, equal or greater? Text collation, null treatment, data type and operator class affect ordering. “Alphabetical” is not one universal mathematical order across languages and collations.
PostgreSQL's official B-tree index documentation describes its B-tree as a multiway balanced tree and explains that data types with a well-defined linear sort order can be indexed through suitable operator classes. The current documentation is a useful primary reference because implementation details and supported features can evolve.
What Makes a B-Tree Balanced
A search tree stores separator keys in internal nodes. Each separator directs the search toward a child covering a key range. Leaf nodes hold index entries that refer to table rows or contain enough information for certain index-only operations.
A B-tree maintains all leaves at the same depth. Balance prevents one unlucky key range from becoming a very long chain while another remains shallow.
A simplified node
Suppose an internal node contains separator keys 20, 50 and 80. It has four child ranges:
- keys less than 20;
- keys from 20 up to but below 50;
- keys from 50 up to but below 80;
- keys 80 and above.
A search for 63 follows the third child. The exact boundary convention and duplicate handling depend on implementation, but the routing idea is stable.
Minimum occupancy
Textbook B-tree definitions use an order or minimum degree that constrains how many keys and children non-root nodes may contain. Real database implementations add page headers, tuple formats, variable-length keys, deduplication, concurrency rules and recovery information.
The occupancy constraint keeps the tree from becoming arbitrarily sparse. Yet full pages cannot absorb another entry, so insertions may trigger splits.
The root is special
The root can have fewer entries than ordinary internal nodes. As the index grows, a root split creates a new root and increases tree height by one. As data are removed or reorganised, implementations may reclaim or merge space according to their rules.
Branching Factor and Logarithmic Height
If each internal page has about \(b\) children and the tree has height \(h\), it can address roughly
\[ b^h \]
leaf regions in a simplified full-tree model. Solving for height gives
\[ h\approx\log_b N=\frac{\ln N}{\ln b}. \]
Large branching factor makes height small.
A scale example
Suppose an idealised internal page routes to 200 children. A three-level routing capacity is
\[ 200^3=8{,}000{,}000. \]
Four levels give
\[ 200^4=1.6\times10^9. \]
This is not a promise that a four-level index stores exactly 1.6 billion rows. Pages are not perfectly full, key sizes vary, leaves contain multiple entries and database details matter. The calculation explains why high fan-out can keep enormous indexes shallow.
Height versus total work
Reaching a leaf is only part of a query. After finding the first matching key, the database may read many neighbouring leaf entries and table rows. A query matching 500,000 rows does not become \(O(\log n)\) in total merely because the first row was found logarithmically.
A more honest model is
\[ T(n,k)=O(\log_b n+k), \]
where \(k\) represents output or matched-entry work under simplifying assumptions.
A Worked Search Example
Consider a simplified three-level B-tree. The root contains separators 300 and 700. The middle child covers keys 300 through 699 and contains separators 420, 540 and 620. Its third child covers 540 through 619 and leads to a leaf containing
\[ [542, 551, 576, 590, 604, 617]. \]
To search for 590:
1. Compare at the root: 590 lies between 300 and 700. 2. In the middle internal page: 590 lies between 540 and 620. 3. Search the chosen leaf and find 590.
The tree avoided every branch outside those ranges. If the pages were already cached, comparisons dominate; if not, the important benefit is limiting page reads.
Search for a missing key
Search for 600. The same first two routing decisions reach the same leaf. Within the sorted leaf, 600 belongs between 590 and 604, so the absence is established without checking unrelated leaves.
This is a valuable idea: a well-structured index can prove non-membership efficiently, not only find present values.
Audit the example
Every separator convention must be consistent. If one child is described as “less than” while the neighbouring child also includes the boundary, duplicate routing becomes ambiguous. A diagram should label half-open intervals such as \([300,700)\) or state the implementation's rule.
Insertions, Splits and Write Cost
Suppose the leaf above has capacity six and key 600 is inserted. In sorted order it becomes
\[ [542,551,576,590,600,604,617], \]
which no longer fits. A simplified split divides the entries into two leaf pages and inserts a separator into the parent.
If the parent is also full, the split can propagate upward. In the rare case that the root splits, tree height increases.
Why an index slows some writes
Inserting a table row may require updates to every relevant index. The database must locate the insertion position, write index pages, record changes for durability and coordinate concurrent transactions. More indexes can improve selected reads while increasing write work, storage and maintenance.
An unused index is not free. It may occupy cache space and demand updates without helping important queries.
Page fill and locality
Leaving free space can reduce immediate splits but increases index size. Sequentially increasing keys often target the rightmost leaf, while random keys distribute writes differently. Workload shape therefore affects contention, locality and maintenance.
The mathematics does not choose one universal fill factor. It helps teams measure trade-offs under their workload.
Range Queries and Leaf Pages
B-trees are especially useful for ordered comparisons. After locating the first key in a range, the system can walk through adjacent leaf entries until the upper bound is passed.
For a query such as
\[ 450\le x<500, \]
the index finds the lower boundary near 450, then scans forward through matching entries. Leaf pages in PostgreSQL B-trees can be traversed in order through page links, as described in the current PostgreSQL implementation documentation.
Prefix searches and ordering
An ordered index can support some prefix patterns because values sharing a prefix occupy a contiguous range under suitable collation and operator rules. A pattern beginning with an unconstrained wildcard may not provide a useful lower boundary.
The rule is not “B-trees make all text searches fast.” Full-text search, token containment, geographic overlap and similarity may need other index structures.
Sorting without a separate sort
If an index order matches the requested ordering, the database may return rows in index order and avoid a separate sort. Reverse traversal can support descending order in systems that allow it. Mixed column directions and null ordering require a matching definition.
The benefit depends on the query. Reading most of a poorly clustered table through scattered row references may cost more than scanning and sorting once.
Composite and Covering Indexes
A composite index stores several key columns in a defined order. An index on \((school, student\_id)\) is ordered first by school, then by student ID within each school.
The leftmost structure
Queries constraining the first column can identify a contiguous range. A query constraining only the second column may have to examine many school groups because student IDs are not globally ordered by themselves in this index.
PostgreSQL's current multicolumn index documentation explains how leading-column constraints affect scanned portions and how skip-scan optimisation may sometimes help. Because planner capabilities change, current official documentation is better than memorising one permanent slogan.
Column order is a workload decision
Suppose a table has one million rows, 10 schools and 100,000 students distributed evenly. An index on \((school, date)\) can isolate one school's date range. An index on \((date, school)\) groups all schools by date first. Neither order is universally superior.
Choose based on common filters, range conditions, ordering needs, data distribution and write cost. An index designed from one example query may disappoint the rest of the workload.
Covering indexes
A covering index includes all columns needed by a query, potentially allowing an index-only scan when database visibility rules and other conditions permit. The PostgreSQL index-only scan documentation explains included payload columns and why storing wide, seldom-used payloads can bloat an index.
Coverage is therefore another trade-off: fewer table visits for certain reads, more storage and write work for the index.
The Query Planner and Selectivity
The query planner estimates the cost of possible plans. It may compare a sequential scan, index scan, bitmap plan, join methods and other operations. Estimates draw on table size, value statistics, correlations and configured cost assumptions.
Selectivity
Selectivity is the fraction of rows expected to satisfy a condition. If a one-million-row table has 100 equally common status values, an equality condition might naively select about
\[ \frac{1}{100}=1\% \]
or 10,000 rows. Real distributions are rarely perfectly uniform. A status such as “active” might cover 80% of rows while “suspended” covers 0.1%.
Statistics about common values and histograms help the planner avoid the uniformity assumption. Stale or insufficient statistics can lead to poor estimates and poor plan choices.
Independence can fail
Suppose 10% of students are in year 6 and 5% attend a particular programme. Multiplying gives 0.5% if the conditions are independent:
\[ P(A\cap B)=P(A)P(B)=0.10\times0.05=0.005. \]
But if the programme is offered only to year 6, independence is false. Correlated columns require richer statistics or a different estimate.
This is database statistics serving an algorithm. A wrong probability estimate can send the engine toward an access path that is mathematically valid but operationally expensive.
Estimated cost is not elapsed time
Planner cost units combine assumptions about page access, CPU work and row counts. They rank plans; they are not promised milliseconds. Actual execution depends on cache state, concurrency, hardware, parameter values and data changes.
Equality, Uniqueness and Duplicates
A unique index enforces that indexed keys satisfy a uniqueness rule. This is not identical to saying every person, object or concept is unique. The constraint applies to the stored key values under the database's equality and null semantics.
Duplicate non-unique keys may refer to many rows. The index locates the duplicate range, then returns every qualifying entry. If millions of rows share the same key, an equality lookup can still return millions of results.
Primary keys and identifiers
A primary key identifies rows according to the data model. A natural identifier, generated integer or UUID has different storage and distribution properties. Choosing one requires data integrity and workload reasoning, not only index speed.
Collations and case
Text equality and ordering may depend on collation and expression. An index on the original text does not automatically accelerate every function applied to that text. Functional indexes can store a transformed expression when the database supports it, but the query must match the indexed semantics.
Concurrency, Transactions and Correctness
Databases serve many users at once. A search can run while another transaction inserts, updates or deletes keys. The index access method must cooperate with locking, multiversion visibility and crash recovery.
A page split therefore is not only a list operation. Other sessions may hold references to pages or scan neighbouring ranges. The implementation uses protocols so readers see a valid structure during change.
Index correctness is not query correctness
An index can find the rows described by a condition while the overall query still has a logic error. Incorrect joins, missing time boundaries, duplicated rows and misunderstood nulls remain possible.
Testing needs known datasets and invariants. If a query is supposed to return one row per student, count duplicates by student identifier. If a range is half-open, test exact boundary timestamps. Performance and correctness should be measured separately.
A Student Simulation
Students can build a paper or spreadsheet B-tree with a small page capacity.
Step 1: define the rules
Use leaf capacity four and internal capacity four children. State the boundary rule. Insert keys
\[ 30,10,50,20,40,60,70,25,5,55,65,35. \]
Keep each leaf sorted. When a page overflows, split it and promote or copy the appropriate separator according to the chosen simplified B-tree or B+tree convention.
Step 2: count page visits
Search for 55, 26 and 80. Record each visited node. Compare with scanning the full sorted list.
Step 3: run a range query
Find every key in \([25,60)\). Locate 25, then scan neighbouring leaves until 60 is reached. Separate the logarithmic location cost from output cost.
Step 4: model a workload
Generate 1,000 student records with columns school, year and score. Compare three access strategies:
- no index;
- index on school;
- composite index on school and score.
Count examined index entries and rows for several queries. Do not claim the count equals real database time; explain what the model excludes.
Step 5: ask the database
If students have access to a local learning database, create a table with synthetic data and use its plan-explanation command. Change the predicate from rare to common and observe whether the planner changes paths. Never use private school records or a production database for the exercise.
Keep a lab notebook with data size, index definition, query, plan, estimated rows and actual rows. Learning from mistakes means tracing a surprising plan back to selectivity, column order, stale statistics or an invalid assumption.
Common Misconceptions
“An index makes every query faster”
No. It helps queries compatible with its keys and order. Low-selectivity reads, tiny tables or scattered row access may favour a scan.
“B-tree means binary tree”
No. Database B-trees are multiway trees whose pages can contain many keys and child pointers.
“Index lookup is always exactly O(log n)”
Locating the first match can grow logarithmically under the model. Returning \(k\) rows adds work, and page access, cache and concurrency affect actual time.
“More indexes are always better”
Each index consumes storage and needs updates. Redundant or unused indexes can hurt write performance and maintenance.
“A high-cardinality column automatically needs an index”
Cardinality matters, but query patterns, table size, ordering, joins, update rate and plan cost also matter.
“The planner knows exact row counts”
It estimates from statistics and assumptions. Correlation, stale data and parameter-sensitive distributions can produce errors.
Cost Models, Caches and Big-O
Big-O notation describes how work grows and deliberately hides constants and hardware details. Database performance needs both a growth model and a cost model.
Pages can come from different places
A page needed by a query may already be in the database buffer cache, may be in an operating-system cache or may require storage access. These cases can have different latency. A planner cannot know future cache state perfectly, so it uses configurable assumptions and observed statistics.
A B-tree descent of four pages is not automatically four physical reads. The root and upper pages are frequently reused and may remain cached. Conversely, returning many scattered table rows after one quick descent can generate substantial random access.
Startup and total cost
Some plans return a first row quickly but become expensive when all rows are consumed. Others sort or build a structure before returning anything, then process the remainder efficiently. Interactive pagination, aggregation and full export can favour different plans.
The mathematical habit is to define the objective. “Fast” might mean smallest time to first row, smallest total time, least memory, least network traffic or best throughput under concurrency.
A simplified comparison
Suppose a table occupies 50,000 pages. A scan reads them sequentially. An index plan descends four index pages and fetches 200 table pages. With sequential-page cost 1 and random-page cost 4, toy estimates are
\[ C_{scan}=50{,}000 \]
and
\[ C_{index}=4(4+200)=816. \]
The index looks attractive. If 20,000 scattered table pages are expected, the index estimate becomes (4(4+20{,}000)=80{,}016), larger than the scan. These are comparable planning units, not promised milliseconds.
Skew, Correlation and Estimation Error
A planner estimates how many rows satisfy a condition. If a column has 100 distinct values, assuming each occurs one per cent of the time is convenient but can be very wrong.
Frequency skew
Imagine a delivery table in which `delivered` accounts for 92 per cent of rows and `lost` for 0.02 per cent. Both are one value in the same column, but an index predicate on `lost` is much more selective.
Statistics can retain common values and frequencies, but every summary compresses information. Values not represented individually are handled through broader assumptions.
Correlated columns
Suppose `district` and `postal_sector` are strongly related. Treating their conditions as independent multiplies probabilities:
\[ P(A\cap B)\approx P(A)P(B). \]
If the columns are correlated, the product can seriously misestimate matching rows. Extended statistics or a better model may help, but no estimate is perfect.
Why estimates change plans
A plan chosen for 20 expected rows may perform poorly if 200,000 arrive. Row estimates affect join order, join method, memory allocation and whether an index looks worthwhile. Probability assumptions are operational: a bad estimate can cause a system to choose a bad action.
Index-Only Scans and Visibility
An index can sometimes contain every column needed by a query. The engine may then avoid many table visits. PostgreSQL's official guide to index-only scans and covering indexes explains an important qualification: the system must still determine whether a row version is visible to the current transaction.
Payload columns
An index on `student_id` could include `checkout_date` as payload. A query selecting only those fields may be answerable from index entries. This can reduce table access, but payload makes the index larger, reduces entries per page and adds write work.
Visibility is part of correctness
Multi-version concurrency control lets transactions see different row versions. An index tuple alone may not prove that its table row is visible to the current snapshot. Visibility information and recently changed pages influence whether the optimisation pays off.
Skipping a necessary check is not an optimisation if it returns a row the transaction should not see. Correctness sets the boundary for every performance technique.
Compression, Fill Factor and Physical Design
Sorted neighbouring keys often share structure. Implementations may compress prefixes, deduplicate repeated keys or use posting lists to fit more logical entries into a page. The details vary, but the mathematical goal is to exploit redundancy without changing semantics.
If more entries fit, branching factor can rise and the tree may remain shallower. Yet compression costs processing, and variable-length data complicates occupancy. Real page capacity is not simply page bytes divided by visible key length.
Leaving free space can postpone splits during future inserts. Packing every page may save space for a static index but cause more immediate reorganisation under updates. An append-like timestamp index behaves differently from random identifiers or frequently updated keys. Physical design is a hypothesis to test against representative data and writes.
Concurrency, Transactions and Correct Search
While one transaction searches, another may insert, delete or update entries. The tree must remain searchable through structural changes, and recovery must preserve consistency after failure.
Latches and locks
Short-lived internal latches protect pages while they are inspected or changed. Transaction locks protect logical operations and may persist longer. Terminology varies by product, but confusing the concepts produces weak explanations.
Suppose a leaf page splits while another operation navigates the tree. The implementation needs a protocol so the search neither loses moved entries nor follows an invalid pointer. Page links, boundary keys, logging and ordered latch acquisition can participate.
The invariant is more important than one vendor's algorithm: every committed key that should be found must remain reachable under the comparison rules.
Unique indexes and races
A unique index must prevent two transactions from committing duplicate keys even if both initially observe no matching committed row. That requires coordination beyond a simple application read followed by a write. Atomic insertion and transaction rules solve a race ordinary code can mishandle.
Diagnosing a Query with Evidence
A sensible investigation begins with correctness and measurement.
- State the intended result in plain language.
- Inspect the plan and actual row counts on safe representative data.
- Compare estimated and observed rows at important operations.
- Check which predicates become index conditions and which remain filters.
- Measure buffers or page activity when the tool supports it.
- Distinguish warm-cache and cold-cache behaviour.
- Include write cost before adding an index.
Suppose a query filters `school_id=42` and a date range, then sorts newest first. An index on `(school_id, event_time DESC)` may align with equality on the first key, range and order on the second. An index on `(event_time, school_id)` creates a different lexicographic order and may scan many dates across all schools.
This is not a universal recipe. If date is far more selective, or the workload asks another question, a different order may win. The point is to map index order to the query's search interval and requested output.
A Second Worked Example: Height and Capacity
Assume each internal page can route to 250 children and each leaf holds 180 entries. One hundred million entries need about
\[ \left\lceil\frac{100{,}000{,}000}{180}\right\rceil=555{,}556 \]
leaf pages. The level above needs about
\[ \left\lceil\frac{555{,}556}{250}\right\rceil=2{,}223 \]
pages, then about nine pages, then one root. A route from root to leaf crosses four levels in this model.
The calculation is a capacity illustration, not a prediction of real size. Headers, variable keys, occupancy, versions, included columns and implementation features change the numbers. Still, it explains how a vast entry count can sit beneath a shallow tree.
If entries double, height may stay the same until a capacity threshold is crossed. This stepwise growth is why logarithmic structures scale well: doubling data does not double the path length.
Guidance and Pathways
Students should learn arrays, binary search, logarithms, trees, probability and database queries together. The transfer is powerful: a logarithm explains height; a probability estimate helps choose a plan; a data model decides which uniqueness constraint is meaningful.
Useful questions include:
- Which columns are ordered, and in what direction?
- What fraction of rows should match?
- Does the query constrain the leading key?
- How many rows must be returned after the first match?
- Are estimates close to observed counts?
- What does the index cost on inserts and updates?
- Is the query correct before it is made fast?
For parents and teachers, a deck of numbered cards can make the mechanism visible before coding. Let the student split pages, route searches and explain why the tree remains balanced.
Careers include software engineering, data engineering, database administration, analytics, distributed systems and reliability engineering. No one data structure guarantees a career, but the Mathematics Pathways guide helps connect school mathematics to later options without closing them too early.
Useful Next Reading
Recommender systems, similarity and matrix factorisation explains how databases may support a larger predictive system. Differential privacy, random noise and data protection asks how useful aggregate analysis can limit information about individuals.
For wider study routes, continue to the eduKate Sengkang Mathematics Hub or Career Mathematics in the Engineer Series.
Frequently Asked Questions
What is a database index?
It is an auxiliary data structure that helps a database locate rows or produce ordering without examining the whole table in every case.
What is a B-tree?
It is a balanced multiway search tree. Internal pages route key ranges, and leaf pages contain ordered index entries.
Why is a B-tree shallow?
Each internal page can have many children. High branching factor means a small logarithmic height even for large entry counts.
Is a B-tree the same as a binary search tree?
No. A binary tree has at most two children per node; a B-tree node can have many children and is designed around page-based storage.
Why does column order matter in a composite index?
The keys are sorted lexicographically: first by the first column, then by later columns within equal leading values. Queries need compatible constraints to isolate a narrow range.
Why might a database ignore an index?
The planner may estimate that a scan is cheaper because many rows match, the table is small, row lookups are scattered or another plan has lower cost.
Can indexes return wrong data?
A correct database index should preserve its defined semantics, but an application query can still be logically wrong. Performance testing never replaces correctness testing.
Can students experiment safely?
Yes. Use synthetic data in a local learning database, record plans and never practise on private or production records.
Final Perspective: Mathematics Builds the Route to the Row
A database query can look like one sentence, but the engine must choose a route. B-trees use order to divide the search space, branching to keep height small, balance to avoid pathological paths and statistics to decide whether the index is worth using.
That is why mathematics matters in databases. It turns “find it quickly” into a measurable problem involving comparisons, pages, probabilities and trade-offs. The best index is not the one with the most impressive name. It is the one whose structure matches the data, the query and the cost of keeping that structure correct as the database changes.