Data Indexing

Nonspatial Data Indexing

As noted above, nonspatial indexing appears in the implementation of a very large percentage of computer applications. While there are many types of nonspatial indexes, they all allow a program to query a data set or database for specific information much faster than would be possible if the computer had to look through the entire data set or database for that information. The type of index included in a particular application is usually carefully chosen [Page 683]based on certain key properties, such as the additional data storage costs (just like a book's index, data indexes take up additional space), the type of data that will be indexed, and, of course, the speed of lookups. Sometimes the indexing process and the data index type can be very simple. For example, the file with the “.shx” extension that is part of the shapefile specification is purely a rudimentary index file that makes it easier for any program reading the shapefile to find the data related to a specific point, line, or polygon. It is essentially made up of a set of pointers to the beginning of data records in the .shp file.

Figure 1 A diagram of a simplified B-tree index

Source: Author

Many times, however, more complex data index approaches are needed. One important type of nontrivial data index is the B-tree index. Invented in 1972, B-trees and their variants are still vital in modern systems. For example, B-trees are the default nonspatial indexing method in the very popular MySQL database management system. While the details of B-tree implementations are outside the scope of this text, the basic idea of their structure is illustrated in Figure 1.

The shaded entries indicate which “nodes” need to be examined to find the record number “18” (and data about record 18). A “sequential scan” of the “data set” would have had to look at 18 different entries (assuming the data had been presorted), while the B-tree reduces that number to 3.

...