6. Data Storage, File Organization and Indexing

Introduction and Context

A database management system (DBMS) presents data to users as relations, documents, graphs, or other logical structures, but the database ultimately depends on physical storage devices and carefully engineered access paths. The difference between a query that responds in milliseconds and one that consumes minutes is often determined not by SQL syntax, but by how records are arranged on pages, how files are organized, and whether an appropriate index exists.

Storage design is therefore the physical foundation of database performance. It connects logical data modelling with operating-system files, disk and memory hierarchies, access methods, transaction processing, and query optimization. Although modern systems use solid-state drives, distributed storage, and cloud platforms, the central principles remain important: data is transferred in blocks, random access is more expensive than sequential access in many situations, and additional indexes improve some reads while increasing storage and update costs.

This chapter examines storage hierarchies, records and pages, heap and sorted files, hashing, B-tree and B+ tree indexes, clustered and non-clustered organization, partitioning, and practical storage decisions. The emphasis is not merely on definitions, but on choosing an appropriate organization for a workload.

Learning Objectives

After studying this chapter, the learner should be able to:

1. Explain the relationship among storage devices, buffers, pages, records, and database files.

2. Compare heap, sorted, hashed, clustered, and indexed file organizations.

3. Describe the structure and operation of B-tree and B+ tree indexes.

4. Distinguish clustered indexes from non-clustered indexes.

5. Select storage and indexing strategies for different query and update workloads.

6. Evaluate partitioning, indexing overhead, maintenance requirements, and failure risks.

7. Apply these concepts to a realistic database design problem.

From Storage Hierarchy to Database Page

Database storage is organized as a hierarchy. At the fastest level, the processor uses registers and cache memory. Main memory provides the working area for the DBMS buffer pool. Persistent storage is usually provided by solid-state drives (SSDs), hard disk drives (HDDs), network-attached storage, or cloud block and object services. Archival media may provide lower-cost but slower retention.

The hierarchy creates a fundamental design issue: the complete database cannot normally remain in the fastest storage. A DBMS therefore moves portions of data between persistent storage and memory. The unit transferred is usually a page, also called a block. A page may be 4 KB, 8 KB, 16 KB, or another system-specific size. The DBMS reads a page into a buffer frame, operates on its records, and eventually writes a modified page back to storage.

The cost of a data access includes locating the storage region, transferring the page, and processing its contents. SSDs reduce seek-related delays compared with HDDs, but page transfers and I/O remain substantially more expensive than operations on data already in memory. Consequently, query optimization attempts to reduce the number of page reads, not merely the number of individual comparisons.

A buffer manager controls which pages reside in memory. Frequently used pages may remain in the buffer pool, while less useful pages are evicted according to policies such as least recently used or workload-aware variants. A query that scans a file sequentially can often exploit read-ahead and efficient page utilization. A query that repeatedly follows pointers to scattered pages may cause random I/O and poor cache behavior.

Records and Their Physical Representation

A record is a collection of related fields representing one occurrence of an entity or event. A customer record may contain an identifier, name, address, and credit limit. Records may be fixed-length or variable-length. Fixed-length records simplify offset calculation, whereas variable-length records use less space when fields differ greatly in size but require additional metadata.

A page commonly contains a page header, record data, and free-space information. In a slotted-page design, a slot directory stores pointers or offsets to records. This approach allows records to move within a page without changing their logical identifiers. It is especially useful for variable-length records and for systems that use record identifiers consisting of a page number and slot number.

A record may be identified by a primary key at the logical level and by a physical record identifier at the storage level. These should not be confused. A primary key expresses data integrity and entity identity; a record identifier expresses a current physical location. If a record moves, the DBMS must either update references or use an indirection mechanism.

File Organization as an Access Strategy

A database file is a collection of pages containing records. File organization determines how records are placed and how they are found. No organization is universally best. The appropriate choice depends on whether the workload emphasizes point searches, range searches, sequential analysis, frequent insertion, frequent updates, or large scans.

Heap Files

In a heap file, records are stored in no particular ordering. New records may be placed in any page with sufficient free space, often identified through a free-space map or page directory. Insertion is generally efficient because the system need not preserve an ordering property.

A heap file is suitable when:

• records are frequently inserted;
• queries often scan the whole relation;
• access is primarily through separate indexes; or
• no meaningful ordering attribute exists.

The weakness of a heap file is search. A query without an index may require a scan of every page. Even when an index exists, updates that enlarge records can cause movement, fragmentation, or overflow management.

Sorted or Sequential Files

In a sorted file, records are physically ordered by a search key. Equality and range searches on that key can be efficient, and sequential processing is particularly effective. For example, a transaction file ordered by transaction date can support reporting over a date interval.

Maintaining physical order makes insertion and deletion more expensive. A new record may require space between existing records, page reorganization, or overflow pages. Periodic reorganization may be needed. Sorted files are therefore attractive for relatively stable data and read-intensive workloads, but less attractive for heavily updated operational tables.

Hashed Files

Hash organization applies a hash function to a search key and maps the result to a bucket. A bucket consists of one or more pages. Equality searches such as `WHERE CustomerID = 4812` can be very efficient because the system computes the target bucket rather than searching the entire file.

Hashing is less suitable for range predicates. Records with adjacent key values may be distributed into unrelated buckets, so a query for all values between 4000 and 5000 may require many bucket accesses or a full scan. Collisions occur when different keys map to the same bucket. Overflow pages, chaining, or dynamic hashing methods such as extendible hashing can manage collisions, but excessive overflow reduces performance.

Static hashing assumes a relatively stable file size. When the file grows substantially, bucket occupancy and overflow may become problematic. Dynamic hashing adjusts the bucket structure as data volume changes, although it introduces additional metadata and structural operations.

Indexes: Additional Access Paths

An index is an auxiliary data structure containing search-key values and references to corresponding records or pages. It is similar in purpose to an index in a book: it avoids reading every page when the required data can be located through a narrower structure.

An index may be dense, with an entry for every search-key value or record, or sparse, with entries for only some values. A sparse index generally requires the underlying data file to be ordered on the indexed field. Index entries may contain the complete record, a page pointer, or a record pointer. A secondary index on a non-unique attribute may point to a list or bucket of record identifiers.

Indexes improve read performance but are not free. They consume storage, must be maintained during insertion, deletion, and modification, and may increase logging and recovery work. An index that is never used is a liability. The relevant question is not whether an index is technically possible, but whether its benefit justifies its maintenance cost for the actual workload.

B-Tree and B+ Tree Indexes

Balanced tree indexes are widely used because they support equality searches, range searches, ordered traversal, and dynamic updates. A balanced tree keeps leaf paths at approximately the same length, so access cost remains predictable as the index grows.

A B-tree node contains keys and child pointers, and some implementations permit records or record pointers in both internal and leaf nodes. Nodes are kept within a minimum and maximum occupancy range. When insertion causes overflow, a node splits and a separator key is promoted. When deletion causes underflow, entries may be redistributed with a sibling or nodes may be merged. These operations preserve balance.

A B+ tree is a specialized and widely used form in which internal nodes contain only separator keys and child pointers, while all data entries are stored at the leaf level. Leaf nodes are linked in key order. This structure offers several advantages:

• internal nodes hold more separator keys, increasing fan-out;
• all searches descend to a leaf, giving consistent behavior;
• linked leaves support efficient range scans and ordered output;
• tree height is usually small because each node represents a page and fan-out is high.

For an equality search, the DBMS follows a path from the root to a leaf. For a range search, it finds the first relevant leaf and then follows leaf links until the range ends. Insertions and deletions may split, merge, or redistribute leaf pages, but the index remains balanced.

A B+ tree is not automatically beneficial for every query. If a predicate matches a very large proportion of a table, using the index may require reading many index pages and then many scattered data pages. A sequential scan may be cheaper. The optimizer estimates selectivity, page costs, clustering, and available memory before selecting an access plan.

Clustered and Non-Clustered Indexes

A clustered index determines, or closely corresponds to, the physical order of table data. Because a table can normally have only one physical ordering, it can generally have only one clustered organization. A clustered index is particularly effective for range queries because adjacent index entries tend to refer to adjacent data pages.

A non-clustered index is a separate access structure whose ordering does not determine the physical arrangement of the table. A table can have several non-clustered indexes on different attributes. They are useful for selective equality searches and for supporting alternative query patterns, but a lookup may require additional random accesses to fetch the full records.

The distinction is physical rather than simply semantic. A primary key is not necessarily clustered, and a clustered index is not necessarily defined on a primary key. A system may cluster a table by event date, warehouse location, or another attribute that best supports its dominant workload.

Covering indexes deserve special attention. An index is covering for a query when it contains all columns required by that query, including projected and filtered columns. The DBMS can then answer the query using the index alone, avoiding base-table lookups. However, adding many included columns makes the index larger and more expensive to maintain.

Partitioning and Physical Locality

Partitioning divides a logical table into smaller physical units called partitions. The table remains logically unified, but storage and processing can be managed separately. Common forms include range partitioning, list partitioning, hash partitioning, and composite strategies.

Range partitioning is useful for time-oriented data: records may be divided by month, quarter, or year. A query restricted to one period can benefit from partition pruning, in which irrelevant partitions are excluded before access. List partitioning can separate known categories such as region or business unit. Hash partitioning distributes records according to a hash function and can balance data when no natural range boundary exists.

Partitioning can improve manageability, parallel processing, data lifecycle operations, and recovery. Old partitions may be archived or removed without rewriting the entire table. Nevertheless, partitioning does not replace indexing. A query may still need an index within each relevant partition. Poor partition keys can create skew, excessive metadata, or queries that touch every partition. Cross-partition joins and global uniqueness constraints may also be more complex.

Designing Storage for a Workload

Physical design should begin with workload analysis rather than with a preference for a particular data structure. Important questions include:

• Which queries are most frequent or most time-sensitive?
• Are predicates mostly equality, range, prefix, or full-scan conditions?
• What proportion of rows does each predicate select?
• How often are records inserted, updated, or deleted?
• Is the workload transactional, analytical, or mixed?
• Are data volumes growing rapidly, and is historical data accessed differently from recent data?
• Can the system tolerate maintenance windows for reorganization?

A useful decision pattern is as follows. Choose a heap organization when rapid insertion and flexible access are more important than physical ordering. Choose a sorted or clustered organization when ordered retrieval and range processing dominate. Choose hashing for high-volume equality lookups when range access is unimportant. Choose B+ tree indexes when both equality and range searches, dynamic updates, and ordered traversal are required. Add secondary indexes only when workload evidence demonstrates their value.

Selectivity is central. A highly selective predicate may benefit greatly from an index, while a low-selectivity predicate may be better served by a scan. Index column order also matters for composite indexes. An index on `(CustomerID, OrderDate)` is well suited to searches beginning with CustomerID and may support date ranges within a customer. It is generally less useful for a query filtering only on OrderDate.

Storage design must also consider write amplification. Every additional index can require page modifications, logging, page splits, and cache pressure. Fragmentation, fill factor, stale statistics, and uneven partition sizes can gradually undermine an initially sound design. Monitoring and periodic maintenance are therefore part of physical design, not afterthoughts.

Applied Case: A Retail Order Platform

Background

Consider an illustrative online retailer with a large `Orders` table. Each order has an order identifier, customer identifier, order date, status, total amount, delivery region, and multiple order lines. The operational system receives continuous inserts, while customer-service staff frequently search by order identifier or customer identifier. Analysts generate reports by date and region.

Situation and Analysis

An initial heap table supports insertion effectively, but customer-service searches by customer and date require repeated scans. A single index on order identifier helps exact order searches but does little for customer history or reporting. A full index on every column would improve some searches but would impose excessive update cost.

The workload contains three distinct patterns: highly selective equality searches by order identifier, customer-oriented range searches by date, and large analytical scans over time periods. These patterns should not be forced into one access path.

Approach

The design team adopts the following strategy:

1. A unique B+ tree index on `OrderID` supports direct order retrieval.

2. A composite index on `(CustomerID, OrderDate)` supports customer history and date-range searches for a customer.

3. Orders are range-partitioned by order month, allowing date-restricted reports to use partition pruning.

4. Reporting queries use date and region predicates, with indexes evaluated separately within relevant partitions.

5. Older partitions are moved to lower-cost storage and made read-only after operational retention requirements expire.

6. Index usage, write latency, partition size, and query plans are monitored.

The organization avoids clustering by a volatile status field because frequent status changes would cause physical maintenance and would not support the dominant reporting pattern. It also avoids indexing low-selectivity status alone, since a status value such as “completed” may match most records.

Outcome

Exact order lookups use a short tree path. Customer-service queries avoid full-table scans, and monthly reports read only relevant partitions. Insert overhead remains acceptable because the number of indexes is limited and historical partitions are no longer subject to frequent updates.

Learning Points

The case demonstrates that storage design is workload-specific. Partitioning reduces the amount of data considered, while indexes reduce the search effort within relevant data. Neither technique is universally superior. A design must balance latency, throughput, storage consumption, maintenance, and future growth.

Challenges, Risks, and Common Mistakes

A common mistake is to create indexes solely because a column appears in a query. The index may have poor selectivity, may not match the leading-column rules of a composite index, or may be bypassed because a table scan is cheaper. Another mistake is to ignore write workloads. An index that improves a report by a few milliseconds may be unacceptable if it substantially delays high-volume inserts.

Poor physical design can also produce hot spots. Sequential identifiers may concentrate new records on one page or partition, creating contention in highly concurrent systems. Conversely, random keys can distribute writes but cause poor locality and more page splits. Data skew can overload particular hash buckets or partitions. Statistics that do not reflect current distributions can lead the optimizer to choose inappropriate plans.

Fragmentation and page splits may increase storage and I/O costs. Rebuilding indexes indiscriminately can consume resources and interfere with production workloads; maintenance should be based on measurable benefit. Partitioning too finely can create management overhead, while partitioning too coarsely may provide little pruning benefit.

Governance, Security, and Professional Considerations

Physical design also has governance implications. Indexes and replicas can create additional copies of sensitive data. A covering index may include personally identifiable information that was not intended to be broadly accessible through an operational table. Access controls, encryption, retention rules, and secure disposal must therefore apply to indexes and storage replicas as well as base tables.

Partitioning by geography or business unit may support data-residency requirements, but it does not by itself enforce authorization. Database administrators and data engineers should document storage decisions, ownership, retention periods, recovery objectives, and operational dependencies. Changes to indexes and partitions should be tested, version-controlled, and monitored because a physical-design change can alter query plans and service-level performance.

Contemporary Directions

Modern database platforms increasingly automate physical design by observing query workloads, recommending indexes, adjusting statistics, and, in some cases, creating or removing indexes under controlled policies. Cloud databases may separate compute from storage and use distributed, columnar, or tiered storage. Column-oriented formats are particularly effective for analytical scans because they read only required columns and compress similar values efficiently.

Distributed databases introduce additional concerns, including data locality, sharding keys, replication, cross-node communication, and rebalancing. A partition key that appears appropriate in a single-node system may create network hotspots in a distributed architecture. Adaptive caching, compressed indexes, learned access methods, and storage-class management are active areas of development, but automation does not eliminate the need for workload analysis, governance, and human review.

Best Practices for Physical Storage Design

1. Begin with representative workload measurements rather than assumptions.

2. Keep frequently accessed data physically close when locality benefits the workload.

3. Use B+ tree indexes for dynamic equality and range access unless evidence favors another method.

4. Match composite-index column order to common predicates and ordering requirements.

5. Avoid redundant and unused indexes.

6. Consider selectivity, covering potential, write cost, and storage growth together.

7. Use partitioning when it improves pruning, lifecycle management, parallelism, or recovery.

8. Monitor execution plans, page read counts, cache behavior, index usage, and maintenance cost.

9. Refresh statistics and address fragmentation according to measured need.

10. Include security, retention, backup, recovery, and data-residency requirements in physical design.

Chapter Summary

Database performance depends substantially on how logical data is represented in persistent storage. Pages are the principal units of transfer between storage and the buffer pool, while records and page layouts determine space use and physical movement. Heap files favor flexible insertion, sorted files favor ordered access, and hashed files favor equality searches. Indexes create additional access paths, with B+ trees offering balanced equality, range, and ordered retrieval. Clustered organizations improve locality for selected access patterns, whereas non-clustered indexes provide alternative paths at additional maintenance cost. Partitioning divides a logical table into manageable physical units and can enable pruning and lifecycle operations. Sound design requires workload analysis, attention to selectivity and data locality, monitoring, governance, and a careful balance between read performance and write overhead.

Key Terms

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

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

Record: A collection of related fields representing one entity occurrence or event.

Heap file: A file organization in which records are stored without a required ordering.

Sorted file: A file whose records are physically ordered by a search key.

Hashing: A method that maps a search-key value to a storage bucket.

Bucket: A storage location, usually one or more pages, used by a hash organization.

Index: An auxiliary structure that provides an alternative path to records.

Search key: An attribute or set of attributes used to locate records through an access method.

Dense index: An index containing an entry for every search-key value or record.

Sparse index: An index containing entries for only some search-key values, usually over ordered data.

B-tree: A balanced multiway search tree supporting dynamic insertion and deletion.

B+ tree: A balanced tree whose data entries are stored at linked leaf nodes.

Clustered index: An index or organization that corresponds closely to the physical order of table data.

Non-clustered index: A separate index whose order does not determine table-record placement.

Covering index: An index containing all data needed to answer a particular query.

Partitioning: Dividing a logical table into separately managed physical partitions.

Partition pruning: Excluding irrelevant partitions from query processing.

Selectivity: The proportion of rows satisfying a predicate.

Fragmentation: Inefficient physical distribution of pages or free space caused by data modifications.

Review Questions

Short Answer Questions

1. Why does a DBMS transfer pages rather than individual fields between storage and memory?

2. State one important strength and one weakness of heap files.

3. Why are hash files generally unsuitable for range queries?

4. What is the principal structural difference between a B-tree and a B+ tree?

5. What is meant by partition pruning?

Long Answer Questions

1. Explain the storage hierarchy and describe the role of the buffer manager in database performance.

2. Compare heap, sorted, and hashed file organizations for transactional and analytical workloads.

3. Explain B+ tree search, insertion, deletion, and leaf-level range scanning.

4. Distinguish clustered and non-clustered indexes, including their effects on range access and maintenance.

5. Discuss the major factors that should guide a physical storage and indexing design.

Analytical / Application Questions

1. A table receives thousands of inserts per minute and is queried mainly by exact customer identifier and occasionally by date ranges. Recommend a file organization and indexes, and justify your choices.

2. A monthly report reads 70 percent of a large table, while a customer-service query reads fewer than ten records. Explain why the optimizer might choose a scan for the report and an index for the service query.

3. A partitioned table has one extremely large region partition and many small partitions. Analyze the likely performance and management problems and propose corrective actions.

22. Multiple Choice Questions with Answers

Question 1

Which file organization is generally most appropriate for high-volume equality searches when range searches are not important?

A. Heap organization

B. Hash organization

C. Sorted organization

D. Columnar organization

Correct Answer: B. Hash organization

Question 2

What is a principal advantage of storing data entries only at the leaf level of a B+ tree?

A. All searches can avoid the root node

B. Internal nodes can have higher fan-out and leaves can support ordered scans

C. Range queries require random bucket access

D. Record updates never require structural changes

Correct Answer: B. Internal nodes can have higher fan-out and leaves can support ordered scans

Question 3

A query filters on CustomerID and then requests orders within a date range. Which index is most directly aligned with this access pattern?

A. An index on OrderDate alone

B. An index on Status alone

C. A composite index on CustomerID, OrderDate

D. A hash index on OrderDate alone

Correct Answer: C. A composite index on CustomerID, OrderDate

Question 4

Why may a sequential scan be cheaper than using an index for a low-selectivity query?

A. Indexes cannot support selection predicates

B. The query may need to fetch a large proportion of scattered table pages

C. Sequential scans always use less memory than indexes

D. B+ trees support only equality searches

Correct Answer: B. The query may need to fetch a large proportion of scattered table pages

Question 5

Which statement best describes a clustered index?

A. It contains no pointers to table records

B. It determines or closely follows the physical order of table data

C. It can be created only on a foreign key

D. It is always non-unique

Correct Answer: B. It determines or closely follows the physical order of table data

Question 6

What is the main purpose of partition pruning?

A. To remove duplicate index entries

B. To exclude partitions that cannot contain rows relevant to a query

C. To convert a heap file into a hash file

D. To force every partition to be scanned in parallel

Correct Answer: B. To exclude partitions that cannot contain rows relevant to a query

Question 7

Which consequence is most likely when many secondary indexes are added to a frequently updated table?

A. Updates become less expensive

B. The table automatically becomes clustered on every indexed attribute

C. Additional storage, logging, and index-maintenance costs arise

D. Range queries become impossible

Correct Answer: C. Additional storage, logging, and index-maintenance costs arise

Question 8

A hash-organized file has many overflow pages. What does this most directly indicate?

A. The hash structure may have poor distribution or insufficient bucket capacity

B. The file is perfectly ordered for range searches

C. The buffer pool is necessarily too large

D. The table has no duplicate values

Correct Answer: A. The hash structure may have poor distribution or insufficient bucket capacity

Question 9

Which situation most strongly supports range partitioning by month?

A. Queries and retention operations are primarily organized by time period

B. All queries use a single random identifier

C. The table has no date attribute

D. The system must prevent all updates

Correct Answer: A. Queries and retention operations are primarily organized by time period

Question 10

Why can a covering index improve query performance?

A. It eliminates the need to maintain statistics

B. It contains all columns needed by the query, avoiding base-table lookups

C. It guarantees that every predicate is selective

D. It prevents page splits during insertion

Correct Answer: B. It contains all columns needed by the query, avoiding base-table lookups