External-Memory Structures and Database Indexing

Introduction

A computer’s memory hierarchy strongly influences the design of data structures. A processor can access registers and cache in a few nanoseconds, main memory in tens to hundreds of nanoseconds, and secondary storage—especially disk—in microseconds or milliseconds. Although solid-state drives reduce latency substantially, storage access remains much slower than accessing RAM. Consequently, a data structure that is efficient in RAM may be inefficient when its data is stored on disk or distributed storage.

External-memory data structures are designed to reduce the number of transfers between fast memory and slower storage. The central design principle is to transfer data in blocks or pages rather than individual records. Database indexes, file organizations, search-engine indexes, and large-scale analytics systems all depend on this principle.

This chapter examines storage hierarchies, paging and caching, B-trees and B+ trees, log-structured merge trees, inverted indexes, and database file organization. It also considers practical design trade-offs, contemporary storage systems, and governance issues surrounding indexed data.

Learning Objectives

By the end of this chapter, you should be able to:

1. Explain why external-memory algorithms optimize I/O operations rather than only CPU operations.
2. Describe pages, blocks, buffering, caching, locality, and replacement policies.
3. Analyze the structure and operations of B-trees and B+ trees.
4. Compare B+ trees with LSM trees for read-heavy and write-heavy workloads.
5. Explain inverted indexes and their use in information retrieval.
6. Select appropriate file organizations and indexing strategies for database applications.
7. Evaluate performance, consistency, storage, security, and operational trade-offs.

1. The Storage Hierarchy and the External-Memory Model

1.1 Levels of storage

A typical hierarchy contains:

The hierarchy works because programs exhibit locality:

• Temporal locality: recently accessed data is likely to be accessed again.
• Spatial locality: data near an accessed address is likely to be accessed soon.
• Sequential locality: accesses may follow an ordered sequence.

Storage devices transfer a page or block containing multiple bytes. Let B be the page size in bytes and N be the number of bytes transferred. The idealized number of page transfers is:

Here, the ceiling function counts a partially used final page as one transfer. This expression assumes that pages are contiguous and that transfer overhead is uniform. Real systems also incur seek, queueing, controller, network, and synchronization costs.

The external-memory model treats computation as occurring in fast internal memory while data resides in external memory. Its principal cost measure is the number of block transfers, often called I/Os. CPU comparisons may be far cheaper than a storage access, so minimizing I/Os is usually the primary objective.

1.2 Latency and bandwidth

Latency is the time before a transfer begins or completes; bandwidth is the rate at which data can be transferred once the operation is under way. Sequential scans often exploit bandwidth effectively. Random access may be dominated by latency, even when the requested record is small.

For a simplified transfer, if L is fixed latency, S is the number of bytes transferred, and R is sustained transfer rate in bytes per second, then:

This model assumes one isolated request and a stable transfer rate. It is useful for comparing small random reads with larger sequential reads, but it omits queueing, parallelism, caching, and device-specific behavior.

2. Pages, Buffering, and Caching

2.1 Pages and buffer pools

A database normally divides a file into fixed-size pages, such as 4 KiB, 8 KiB, or 16 KiB. A page may contain records, index entries, or internal metadata. A buffer pool is a region of RAM that stores copies of pages currently being used.

When a transaction requests a page, the database checks whether it is already in the buffer pool. A hit avoids physical I/O. On a miss, the system chooses a frame, writes the old page if it is dirty, and reads the requested page from storage.

The hit ratio is:

where H is the number of cache hits and M is the number of misses. The miss ratio is 1 − h. If a hit costs t_h and a miss costs t_m, the simplified average access time is:

This assumes that all hits and misses have constant costs and that the miss cost includes the replacement and I/O work. In practice, dirty-page writes and queueing may make misses more expensive than this expression suggests.

2.2 Replacement policies

When the buffer is full, a replacement policy selects a page to remove. Common policies include:

• FIFO: removes the page that entered earliest. It is simple but may discard frequently used pages.
• LRU: removes the least recently used page. It exploits temporal locality but can behave poorly during large sequential scans.
• Clock or second-chance: approximates LRU with lower implementation overhead.
• MRU: removes the most recently used page; this can be effective for some repeated scans.
• Workload-aware policies: distinguish index pages, table pages, sequential scans, and temporary data.

Database buffer managers often do not use a pure operating-system cache policy. They know whether a page is pinned by an active operation, whether it is dirty, and how future access is likely to occur.

2.3 Read-ahead and write management

Read-ahead predicts that subsequent pages will be needed and fetches them in advance. It is valuable for sequential scans and range queries. Write-behind asynchronously flushes dirty pages to storage. A checkpoint records enough information to limit recovery time after failure.

Caching improves performance but introduces correctness requirements. A database must preserve durability: after a committed transaction, its effects must survive an appropriate failure model. Write-ahead logging requires log records describing a change to reach durable storage before the corresponding modified data page is written. This ordering supports recovery using undo and redo operations.

3. B-Trees and B+ Trees

3.1 Motivation

A binary search tree can have logarithmic height in RAM, but its nodes may be too small to use storage efficiently. A disk-oriented tree stores many keys and child pointers in each page. Its high branching factor produces a shallow tree, reducing I/O operations.

A B-tree of order m is commonly defined so that each internal node has at most m children. Terminology varies: some authors define order using the maximum number of keys instead. Therefore, an implementation must specify its convention.

Under the common child-pointer convention, every non-root internal node has at least ⌈m/2⌉ children, and at most m children. A non-root node therefore contains one fewer key than child pointers. The root has special minimum-occupancy rules.

A B-tree maintains sorted keys and subtrees. For a node with separator keys k₁, k₂, …, k_r, child subtrees contain values in corresponding key ranges. All leaves occur at the same depth, giving the tree balanced height.

3.2 Search, insertion, and deletion

To search for a key, the algorithm:

1. Reads the root page.
2. Searches the keys within that page.
3. Selects the child interval containing the target.
4. Repeats until the target is found or a leaf proves absence.

If the tree has height h, the search requires approximately h page reads when relevant pages are not cached. Within each page, binary search or optimized key search may be used.

Insertion first locates the target leaf. If there is room, the key is inserted in sorted order. If the page is full, it splits into two pages, and a separator key is promoted to the parent. Splits may propagate to the root, increasing tree height by one.

Deletion may leave a node below minimum occupancy. The implementation can redistribute entries from a sibling or merge nodes. Merging may propagate toward the root.

3.3 Height analysis

If each internal node has at most m children and the tree has height h, its capacity grows approximately as m^h. Thus, a rough upper bound on height is:

where N is the number of indexed entries and m is the effective branching factor. This is an approximation because root occupancy, minimum fill factors, duplicate keys, record size, and page layout affect the actual height.

For example, suppose a tree has an effective fan-out of 100 and 1,000,000 entries. Since 100³ = 1,000,000, three levels of branching can address roughly one million leaf regions. A real tree may require an additional level because leaves contain multiple entries, pages are not completely full, and internal keys have variable sizes.

3.4 B+ trees

A B+ tree stores search keys and child pointers in internal nodes, while actual record pointers or records are stored in leaves. Leaf pages are linked in key order. This arrangement has several benefits:

• Internal nodes hold more separators because they do not store complete records.
• Range queries can find the first leaf and then follow leaf links sequentially.
• All successful data searches reach the leaf level, simplifying traversal.
• Leaf scans are efficient and can use read-ahead.

A composite index on attributes (A, B) is ordered lexicographically: rows are first ordered by A, and ties are ordered by B. It efficiently supports predicates on A and ranges beginning with A, but generally cannot efficiently support a predicate only on B without additional structure. This is the leftmost-prefix principle.

3.5 Clustered and secondary indexes

A clustered index determines the physical or logical order of table records. A table can usually have only one physical clustering order, although a database may maintain multiple logical structures. A secondary, or nonclustered, index stores keys and record identifiers separately from the table’s primary organization.

An index is useful when its reduction in data-page reads exceeds its maintenance and storage costs. It may be ineffective when:

• The predicate is not selective.
• The table is very small.
• The indexed column has low cardinality.
• The query applies a function that prevents direct index use.
• The optimizer estimates that a sequential scan is cheaper.

4. Log-Structured Merge Trees

4.1 Design principle

B+ trees update pages in place. Random updates can cause many page writes, especially on storage systems where sequential writes are cheaper than random writes. An LSM tree instead buffers updates in memory, writes immutable sorted runs sequentially, and periodically merges those runs.

A typical LSM architecture contains:

1. A mutable in-memory structure, often a memtable.
2. A write-ahead log for recovery.
3. Immutable on-disk sorted-string tables, commonly called SSTables.
4. Bloom filters and sparse indexes to avoid unnecessary reads.
5. Compaction processes that merge sorted files.

Figure: Main components and data flow in an LSM-tree-based storage engine.

When a memtable reaches a threshold, it is frozen and flushed as a sorted immutable file. Compaction merges files, removes obsolete versions and tombstones when safe, and creates larger sorted runs.

4.2 Read and write trade-offs

LSM trees often provide high write throughput because updates are accumulated and written sequentially. However, a read may need to check the memtable and several SSTables. Bloom filters probabilistically indicate whether a key is absent from a file. A false positive causes an unnecessary read; a false negative should not occur in a correctly implemented Bloom filter.

Compaction consumes CPU, I/O bandwidth, and temporary storage. Write amplification is the ratio of total bytes written by the storage engine to the logical bytes written by the application:

This is a workload-dependent engineering metric, not a universal constant. High write amplification can reduce device lifetime and interfere with foreground requests.

B+ trees generally provide predictable point and range reads and support in-place updates. LSM trees generally favor sustained writes and can scale across distributed systems, but require careful tuning of compaction, levels, memory, and read amplification.

5. Inverted Indexes and Search Systems

A database index maps structured keys to records. An inverted index maps terms to the documents or records in which they occur. It consists primarily of:

• A dictionary of terms.
• A postings list for each term.
• Optional term frequency, field, position, and payload information.

For documents:

• D1: “data structures support search”
• D2: “search systems use indexes”
• D3: “data indexing supports analytics”

The term “search” has postings [D1, D2], while “data” has [D1, D3]. A query for “data AND search” intersects these sorted lists and returns D1.

5.1 Boolean and ranked retrieval

For Boolean AND, two sorted postings lists can be intersected with two pointers. If their lengths are p and q, the basic intersection takes O(p + q) comparisons. Selecting the shorter postings list first often reduces work for multi-term queries.

Ranked retrieval may use term frequency and inverse document frequency. A common inverse document frequency definition is:

where N is the number of documents and df_t is the number of documents containing term t. The logarithm base changes scale but not ordering. This formula assumes df_t > 0; systems usually handle absent terms separately.

A simple term-frequency–inverse-document-frequency weight is:

where TF(t,d) measures the frequency of term t in document d. Practical systems often use logarithmic term-frequency normalization, document-length normalization, field weights, or probabilistic ranking such as BM25.

5.2 Index construction

Large indexes are often built using blocked sort-based indexing:

1. Read a batch of documents.
2. Tokenize, normalize, and remove or retain stop words according to requirements.
3. Produce term–document pairs.
4. Sort pairs in memory.
5. Write a temporary sorted block.
6. Merge blocks into the final index.

This process resembles external merge sort. It is appropriate when the dictionary and postings do not fit in RAM. Index compression—such as gap encoding of sorted document identifiers—reduces storage and I/O, but requires decoding during queries.

6. File Organization and Database Access Paths

6.1 Heap files

A heap file stores records without maintaining a meaningful order. Inserts are simple and may use free-space maps. Searching for an arbitrary value generally requires a scan unless an auxiliary index exists. Heap organization is useful for write-heavy staging tables and when access is primarily through indexes.

6.2 Sorted or sequential files

Records are stored in key order. Binary search can locate a region, and range scans are efficient. Inserts may be expensive because records must be moved or overflow pages maintained. Periodic reorganization may be necessary.

6.3 Hashed files

A hash function maps a search key to a bucket. Hash organization provides efficient equality lookup when the hash distribution is good. It is not naturally suited to ordered range predicates such as “salary between two values.” Dynamic hashing methods, including extendible hashing, allow buckets to expand as data grows.

6.4 Columnar organization

Row storage keeps all attributes of a record together and is usually effective for transaction processing, where complete records are frequently inserted or updated. Columnar storage keeps values of the same attribute together and is often effective for analytical queries that read a few columns from many rows.

Column stores benefit from compression because adjacent values often have similar types or distributions. They also support vectorized execution, in which an operator processes batches of values rather than one record at a time. However, frequent single-row updates can be more complicated and expensive.

7. Worked Example: Choosing an Access Path

Consider a table containing 10,000,000 fixed-size records. A page holds 100 records, so the table occupies approximately:

Assume a query selects records using a unique indexed identifier and the B+ tree has three internal-to-leaf levels, with the relevant pages not cached. A point lookup may require approximately four page reads: one for the root, two for internal levels, and one leaf, followed by a data-page read if the index is not covering. Thus, the access may require about five reads.

A full table scan requires approximately 100,000 page reads. If the query returns a very large fraction of the table, however, the index may cause many scattered data-page reads. In that case, a sequential scan can be faster despite reading more logical records. The optimizer must compare estimated I/O, caching, selectivity, parallelism, and physical layout rather than apply the rule “indexes are always faster.”

If a covering index contains every column needed by the query, the data-page read may be avoided. The index consumes additional storage and increases insert/update cost, so it should be justified by recurring workload value.

8. Illustrative Case: A Retail Search and Analytics Platform

Background

This illustrative case concerns a retailer with 500 million product, customer, order, and event records. The system supports transactional order processing, keyword product search, and daily analytical reports.

Problem

A single row-oriented heap design produced slow product searches and expensive reports. Secondary indexes improved point lookups but increased write cost. During promotional events, ingestion competed with analytical scans.

Analysis

The workloads differed substantially:

• Order processing required low-latency equality lookups and updates.
• Product search required term matching, ranking, and filtering by price and category.
• Reporting required scans over a small subset of columns and aggregation by time and region.
• Event ingestion was append-heavy and arrived in bursts.

A single index structure could not optimize all four workloads. Excessive secondary indexes would increase maintenance and storage consumption.

Approach and solution

The platform adopted a polyglot storage design:

1. Transactional tables used row-oriented storage with B+ tree indexes on order identifiers, customer identifiers, and selected foreign keys.
2. Product text was processed into an inverted index with postings for terms, fields, and positions.
3. Product filters used B+ trees or equivalent sorted indexes for category, price, and availability.
4. Event data was appended to partitioned columnar files organized by event date.
5. High-ingestion streams used an LSM-based store, with compaction monitored during peak periods.
6. Buffer pools and read-ahead were tuned separately for transactional access and analytical scans.
7. Retention and deletion policies removed obsolete event data and protected customer information.

Outcome

Point lookups became predictable, text queries avoided full scans, and reports read only required columns and partitions. The design introduced operational complexity: multiple systems required data synchronization, schema governance, monitoring, and recovery procedures.

Learning points

The case demonstrates that indexing is a workload-design problem. A structure should be selected according to access patterns, update frequency, selectivity, durability requirements, and operational constraints. It also shows that partitioning, caching, and file organization are complementary rather than interchangeable techniques.

9. Limitations, Governance, and Professional Practice

9.1 Performance limitations

No index eliminates all costs. Indexes consume storage, increase write amplification, require vacuuming or compaction in some systems, and may become fragmented. Statistics can become stale, causing a query optimizer to choose poor plans. Skewed distributions can invalidate uniformity assumptions.

Distributed systems add network latency, replication overhead, partition imbalance, and consistency trade-offs. A local index may be fast but incomplete if data is partitioned across nodes. Global indexes can simplify queries but are more expensive to maintain.

9.2 Consistency and recovery

Index updates must remain consistent with the records they reference. Transactions, write-ahead logs, checksums, snapshots, and recovery testing are essential. A system should specify whether indexes are synchronously maintained, asynchronously updated, or rebuilt from authoritative data.

9.3 Security and privacy

Indexes can expose sensitive information even when the base table is protected. Search terms, document identifiers, and access patterns may reveal personal or confidential data. Security controls should include authentication, authorization, encryption in transit and at rest, audit logging, least privilege, and appropriate retention policies.

Deletion is especially important. A deleted record may persist in backups, immutable runs, logs, replicas, caches, or search indexes. Governance procedures must define how legal deletion requests propagate through each layer.

9.4 AI and contemporary systems

AI and machine-learning systems increasingly use vector indexes for similarity search. Structures such as approximate nearest-neighbor graphs and quantized vector indexes are related to external-memory indexing because they trade accuracy, memory, computation, and I/O. They do not replace B+ trees or inverted indexes: structured filters, exact identifiers, text terms, and vector similarity often require a hybrid retrieval architecture.

Modern systems also exploit NVMe SSDs, persistent memory, distributed object stores, tiered storage, and computational storage. The fundamental principles remain unchanged: exploit locality, minimize expensive transfers, preserve correctness, and measure the actual workload.

Best-Practice Checklist

• Measure I/O, cache hit rate, latency, throughput, and write amplification.
• Choose page size according to record size, access pattern, and device behavior.
• Design indexes from real query predicates and ordering requirements.
• Consider selectivity and covering indexes, not merely column popularity.
• Use B+ trees for ordered access and predictable range scans.
• Consider LSM designs for sustained write-heavy workloads, while monitoring compaction.
• Use inverted indexes for term-to-document retrieval rather than repeated table scans.
• Partition large datasets by a meaningful, commonly filtered attribute such as time.
• Keep statistics current and inspect execution plans.
• Test recovery, deletion propagation, security controls, and worst-case workloads.

Chapter Summary

External-memory structures are designed around the cost of transferring pages between fast and slow storage. Storage hierarchies reward temporal, spatial, and sequential locality, while buffer pools, caching, read-ahead, and replacement policies reduce physical I/O. The external-memory model therefore evaluates algorithms largely by block transfers.

B-trees and especially B+ trees provide balanced, shallow indexes with efficient equality and range searches. Their fan-out reduces height, while linked leaves support ordered scans. LSM trees improve write throughput by buffering updates and merging immutable sorted files, but they introduce read amplification and compaction costs. Inverted indexes support efficient keyword retrieval through dictionaries and postings lists, and external sorting enables their construction at scale.

Heap, sorted, hashed, row-oriented, columnar, and append-oriented files serve different workloads. Effective database design combines file organization, indexing, caching, partitioning, and workload-aware optimization. Professional practice must also address durability, recovery, security, privacy, deletion, distributed operation, and measurement. No structure is universally best; the correct choice depends on workload, scale, access patterns, and governance requirements.

Key Terms

External-memory model: A model that measures computation primarily by transfers between internal and external memory.

Page: A fixed-size unit of data transferred between storage and memory.

Block transfer: Movement of one page or block between storage levels.

Buffer pool: Main-memory area used to cache database pages.

Locality: The tendency of programs to reuse nearby or recently accessed data.

Cache hit: An access satisfied from a cache without slower storage I/O.

B-tree: A balanced multiway search tree designed for block-oriented storage.

B+ tree: A B-tree variant that stores records or record pointers in linked leaf pages.

Fan-out: The number of child pointers or branches supported by an internal node.

Clustered index: An index whose order corresponds to the organization of table records.

Secondary index: An additional index separate from the table’s primary organization.

LSM tree: A structure that buffers updates and merges immutable sorted runs.

Memtable: An in-memory mutable component of an LSM tree.

SSTable: An immutable, sorted on-disk table used by LSM systems.

Compaction: Merging sorted files and removing obsolete versions or tombstones.

Bloom filter: A probabilistic structure that can identify definite absence but may report false presence.

Inverted index: A mapping from terms to documents or records containing them.

Postings list: The list of document or record identifiers associated with an indexed term.

Columnar storage: Organization that stores values of the same attribute together.

Write amplification: The ratio of system-level bytes written to application-level bytes written.

Review Questions

Short Answer Questions

1. Why do external-memory algorithms focus on page transfers rather than only CPU comparisons?
2. Distinguish temporal locality from spatial locality.
3. What is the principal structural difference between a B-tree and a B+ tree?
4. Why can a Bloom filter produce false positives but should not produce false negatives?
5. Give one workload for which columnar storage is especially appropriate.

Long Answer Questions

1. Explain how a database buffer pool processes a page hit and a page miss, including the role of dirty pages and replacement policies.
2. Describe B+ tree search, insertion, splitting, deletion, and range scanning.
3. Compare B+ trees and LSM trees with respect to writes, reads, compaction, storage, and operational complexity.
4. Explain how an inverted index is constructed and how postings-list intersection supports Boolean search.
5. Discuss how row, columnar, heap, sorted, and hashed file organizations serve different database workloads.

Analytical / Application Questions

1. A table has 20 million records and each page stores 200 records. Estimate the number of pages required. Explain when an index lookup might still be slower than scanning those pages.
2. Design an indexing strategy for a service that supports exact customer lookup, date-range order queries, keyword product search, and append-heavy event analytics. Justify each structure.
3. A write-heavy LSM system experiences increasing read latency during compaction. Analyze at least three possible causes and propose measurement-based remedies.

Multiple Choice Questions with Answers

Question 1

What is the primary cost measure in the external-memory model?

A. Number of CPU registers

B. Number of block transfers

C. Number of source-code statements

D. Number of network users

Correct Answer: B. Number of block transfers

Question 2

Which property means that recently accessed data is likely to be accessed again?

A. Temporal locality

B. Spatial locality

C. Referential integrity

D. Hash uniformity

Correct Answer: A. Temporal locality

Question 3

What is a major advantage of a B+ tree over a conventional B-tree for range queries?

A. It eliminates all page splits

B. Its leaves are linked in key order

C. It stores no keys in internal nodes

D. It requires no buffer pool

Correct Answer: B. Its leaves are linked in key order

Question 4

If an index tree has effective fan-out 100, approximately how many branching levels can address one million leaf regions?

A. 1

B. 2

C. 3

D. 10

Correct Answer: C. 3

Question 5

Which operation is characteristic of an LSM tree?

A. Compacting immutable sorted runs

B. Replacing every record with a hash value

C. Storing all records only in CPU registers

D. Sorting data only after every query

Correct Answer: A. Compacting immutable sorted runs

Question 6

What does a Bloom filter guarantee when correctly implemented?

A. Every positive result is certain to be present

B. It never reports absence for a present key

C. It never reports presence for an absent key

D. It always returns exact frequency counts

Correct Answer: B. It never reports absence for a present key

Question 7

An inverted index primarily maps:

A. Pages to buffer frames

B. Terms to documents or records

C. Transactions to processors

D. Rows to database users

Correct Answer: B. Terms to documents or records

Question 8

Which file organization is most naturally suited to equality lookup but not ordered range queries?

A. Hash organization

B. Sorted organization

C. Columnar organization

D. Sequential leaf organization

Correct Answer: A. Hash organization

Question 9

A table has 10,000,000 records and each page stores 100 records. Approximately how many pages does the table occupy?

A. 1,000

B. 10,000

C. 100,000

D. 1,000,000

Correct Answer: C. 100,000

Question 10

What does write amplification measure?

A. The ratio of system bytes written to application bytes written

B. The ratio of cache hits to cache misses

C. The number of keys in an inverted index

D. The number of levels in a B+ tree

Correct Answer: A. The ratio of system bytes written to application bytes written