ABSTRACT
The bulk of the index structures are hierarchical disk-based structures. They pay special attention to the organization of data at the disk level. Since fetching data from a random location on disk, i.e., the random I/O operation, is much more costly than fetching data from consecutive locations, i.e., the sequential I/O operation, the structures focus mostly on saving the random I/O costs. (See Appendix A for details on this comparison.) The CPU costs on processing the data once they are brought to memory is negligible as compared to these costs.
