For a table's primary key to be useful, we must be able to quickly retrieve a data entry when given its ID value. To that end, the DBMS builds an auxiliary index, mapping row IDs to their respective addresses in memory. An index is essentially a self-balancing binary search tree (sec. 4.3). Each row in the table corresponds to a node in the tree.
