A variety of elegant data structures are available for implementing secondary indices. Conceptually, these data structures can be thought of as a set of pointers that link the physical records in the desired secondary order. For instance, if Presidential Number is used as the primary key of the President table, then the first five physical records would be Washington, Adams, Jefferson, Madison and Monroe since they were the first five Presidents of the United States. Obviously, these five records are not in alphabetical order. A secondary index on name would link the records in Adams, Jefferson, Madison, Monroe and Washington order.
What happens when the sixth President (J.Q. Adams) is added to the table? Well, he gets added as the sixth physical record (i.e., after Monroe), but he also gets inserted between J. Adams and T. Jefferson in the name index. That takes time. But, hopefully, the presence of the index will save more total time during search queries than it takes to maintain it when records are changed.
