Which data structure is commonly used to implement database indexes, and what does it store?

Which data structure is commonly used to implement database indexes, and what does it store?

• A. B-trees storing a sorted copy of the indexed columns.
• B. Hash tables storing a sorted copy of all table rows.
• C. Linked lists of data blocks in original order.
• D. Bitmap indexes storing bitmaps for each value.

Answer: (A)

Database indexes are built to locate rows quickly by their indexed values and to support ordered access. A B-tree index is designed for this: it stays balanced so searches, inserts, and deletes take logarithmic time even as data grows, and it keeps the indexed values in sorted order. In a B-tree index, the keys are the values of the indexed column(s) and each key has a pointer to the corresponding data row (or to its storage location). The leaves store these key-pointer pairs in order, which makes both exact lookups and range scans efficient because you can traverse the keys in sorted sequence. Why this is the best choice: the sorted keys with pointers enable fast searches and convenient range queries, which are common in database access patterns. Other structures don’t fit as well: a hash table can find exact matches quickly but doesn’t preserve order for range queries; a linked list of data blocks in original order doesn’t provide fast value-based search; and bitmap indexes are great for low-cardinality columns but aren't the general-purpose indexing approach for all columns.

Database indexes are built to locate rows quickly by their indexed values and to support ordered access. A B-tree index is designed for this: it stays balanced so searches, inserts, and deletes take logarithmic time even as data grows, and it keeps the indexed values in sorted order. In a B-tree index, the keys are the values of the indexed column(s) and each key has a pointer to the corresponding data row (or to its storage location). The leaves store these key-pointer pairs in order, which makes both exact lookups and range scans efficient because you can traverse the keys in sorted sequence.

Why this is the best choice: the sorted keys with pointers enable fast searches and convenient range queries, which are common in database access patterns. Other structures don’t fit as well: a hash table can find exact matches quickly but doesn’t preserve order for range queries; a linked list of data blocks in original order doesn’t provide fast value-based search; and bitmap indexes are great for low-cardinality columns but aren't the general-purpose indexing approach for all columns.