What data structure is commonly used to implement a database index for fast lookups?

• A. Hash table
• B. Linked list
• C. B-tree
• D. Graph

Answer: (C)

Indexes in databases are built as structures that keep keys in sorted order and minimize disk I/O. The B-tree fits this purpose best because it is a balanced multi-way search tree where each node can have many children and contain multiple keys. All leaves are at the same depth, so the path from root to leaf is short, keeping the number of disk reads small even for very large datasets. This makes lookups fast and also supports efficient range queries, which are common in database operations. In practice, databases often use a variant called a B+-tree, where all data resides in the leaves and internal nodes guide the search, optimizing both randomness of access and range traversal. By contrast, a hash table offers quick lookups but doesn’t provide ordered data or efficient range scans, a linked list is too slow for large datasets, and a graph isn’t suited for simple indexing. Thus, the common choice for implementing a database index for fast lookups is a B-tree.