Why Data Structures are Crucial in Database Performance

When you search a library catalogue for a single book among millions of records and the result appears in a fraction of a second, something remarkable is happening behind the screen. The database is not reading every record one by one. Instead, it relies on carefully designed data structures that decide where information sits on disk and how quickly it can be reached. The difference between a query that finishes instantly and one that drags on for minutes often comes down to a single design choice: how the data is structured. This is why data structures sit at the very heart of database performance.

Why disk access is the real bottleneck 🔗

To understand the importance of data structures, you first need to understand what slows a database down. Computers store data in two very different places. Main memory (RAM) is fast but volatile, meaning it loses its contents when power is cut. Secondary storage like hard disk drives (HDDs) and solid-state drives (SSDs) is persistent but far slower to access. Most real databases are too large to fit entirely in memory, so they must live on disk and be fetched piece by piece.

Reading from a disk is an input/output (I/O) operation, and it is the slowest part of the entire chain. The latency of physical storage is enormous compared to the near-instant speed of RAM. Disks are organised into fixed-size units called blocks or pages, often 4 KB or 8 KB in size, and the system always transfers a whole block at a time. The key insight for performance is simple: every disk access costs time, and the goal of good design is to answer a query using as few disk accesses as possible.

The role of data structures in database performance 🔗

A data structure is a way of organising data so that it can be stored and retrieved efficiently. In a database, the data structure determines the physical arrangement of records on disk and the path the system follows to find them. A poor structure forces the database to scan large amounts of data; a good one lets it jump almost directly to the answer.

Consider what happens when there is no helpful structure. If records are simply dumped onto disk in the order they arrive, finding one specific record means checking each block in turn until it is found. This is called a full scan, and on a large table it is painfully slow. The database may have to pull in every page, even when only a single row is wanted.

Minimising disk access 🔗

The whole purpose of designing thoughtful data structures is to minimise the number of disk reads needed to satisfy a request. A structure that lets the system locate a record in three or four block reads will always beat one that requires hundreds. This is why database designers obsess over reducing the height of search trees and packing as much useful information into each block as possible. The choice of how records are physically placed on disk directly shapes how fast they can be retrieved.

Choosing the right organisation 🔗

There is no single best structure for every situation. The right file organisation depends on the kind of operations a database performs most often, whether that is inserting new records rapidly, searching for exact matches, or scanning a range of values. A system used mainly for fast equality lookups, such as fetching a member’s record by their unique ID, has very different needs from one that must list all members whose names fall between two letters. Matching the structure to the workload is one of the most important decisions in physical database design.

Overcoming I/O bottlenecks 🔗

An I/O bottleneck occurs when the speed of reading from and writing to disk becomes the limiting factor for the whole system. The processor may be capable of handling millions of operations per second, but if it spends most of its time waiting for the disk to respond, all that processing power is wasted. Data structures are the primary tool for breaking this bottleneck.

Indexes as shortcuts 🔗

The most powerful weapon against I/O bottlenecks is the index. An index is an auxiliary structure, often a separate file, that stores key values along with pointers to the actual location of each record. Instead of scanning a whole table, the database consults the much smaller index, finds the pointer, and goes straight to the right block. Almost every modern database relies on indexes to locate records quickly. The trade-off is that indexes take up extra storage and must be updated whenever data changes, but for read-heavy workloads the savings in disk access are dramatic.

Favouring sequential reads 🔗

Not all disk access is equal. Because of how spinning disks are built, reading data that is laid out in a continuous sequence is much faster than jumping around to scattered locations. Sequential I/O outpaces random I/O by a wide margin. Smart data structures are designed to keep related records close together on disk, so that a single read brings back many useful items at once. Clustering related data into the same pages is a core technique for cutting down on expensive seeks.

The historical evolution of data structures 🔗

The structures used in today’s databases did not appear overnight. They are the result of decades of engineers confronting the same disk-access problem and inventing progressively cleverer solutions. Tracing this evolution makes it easy to see why each advance mattered.

From sequential files to early indexing 🔗

The earliest systems stored records in sequential files, ordered by a key field such as an account number or roll number. Sequential ordering made it possible to read records in order and to use binary search, which was a big improvement over scanning blindly. But it had a serious weakness. Inserting a new record in its correct position meant shifting every record that came after it, an operation that grew unbearably slow as files expanded.

To work around this, engineers added separate index tables. The index listed key values alongside the positions of records, so the system could look up the index first and then jump to the data. As datasets grew, however, the index itself became huge, sometimes needing a second-level index on top of the first. IBM’s Indexed Sequential Access Method combined sequential storage with these indexes to allow both ordered scanning and direct key-based lookups, and it became one of the dominant approaches of its era.

The arrival of B-trees 🔗

The breakthrough came in 1972, when Rudolf Bayer and Edward McCreight published their work on the B-tree, a high-performance structure for managing large datasets stored on disk. Working at Boeing’s research labs, they designed a balanced tree in which each node could hold many keys and point to many children, rather than just two as in a binary tree. This keeps the tree short and wide.

The reason this matters is purely about disk access. A short tree means a search travels through only a few nodes from root to leaf, and since each node corresponds roughly to a disk page, fewer nodes means fewer reads. Bayer and McCreight assumed indexes would be so large that only small parts could fit in memory at once, so reducing reads was everything. The B-tree keeps all its leaves at the same depth, guaranteeing predictable performance even as data grows.

The structure proved so effective that by 1979 B-trees had replaced nearly all other large-file access methods except hashing. A refined variant, the B+ tree, stores all actual data in the leaf nodes and links them together, making range queries especially efficient. Today, relational systems such as MySQL and PostgreSQL build most of their indexes on B-trees or B+ trees, and the same family of structures underpins many file systems too. Their guaranteed worst-case performance for insertion, deletion, and retrieval is exactly what large, busy databases need.

Hashing for direct access 🔗

Running alongside the tree-based methods is a completely different idea: hashing. In a hashed file, a hash function takes the key of a record and computes the address of the disk block, or bucket, where that record belongs. Hashing provides extremely efficient access when the search is an equality condition on a single field, such as looking up a customer by exact account number.

The appeal of hashing is speed for exact-match queries. There is no tree to traverse and no index to scan; the function points almost directly to the record. The limitation is equally clear. Because records are scattered according to the hash value rather than stored in order, hashing cannot efficiently support range queries. Asking for all students who scored between 20 and 30 marks is awkward, since those records may sit in completely unrelated buckets. This is why databases offer both approaches: B-trees and B+ trees for ordered and range access, and hashing where lightning-fast exact lookups dominate.

The thread running through this entire history is consistent. Each new structure was invented to do one thing better than the last: reduce the number of times the system has to touch the disk. From sequential files to indexes, from B-trees to hashing, the story of database performance is really the story of data structures evolving to outsmart the slowest part of the machine.

What do you think? If you were designing the storage for a university’s student records system that mostly fetches individual students by their enrolment number, would you lean towards hashing or a B-tree, and why? And as SSDs continue to narrow the gap between memory and storage speeds, do you think the classic structures built for slow spinning disks will stay relevant, or will entirely new designs take over?

References

1. https://en.wikipedia.org/wiki/B-tree
2. https://www.cs.uct.ac.za/mit_notes/database/htmls/chp11.html
3. https://bcastudyguide.com/unit-3-file-organization/
4. https://en.wikipedia.org/wiki/ISAM
5. http://www.scholarpedia.org/article/B-tree_and_UB-tree
6. https://opendsa.org/OpenDSA/Books/Catalog/html/BTree.html
7. https://mathworld.wolfram.com/B-Tree.html