Geographic Information Systems: An Introduction, 3rd Edition

12.4 Partitioning and Indexing

We have ascertained that spaghetti data require a long search time inasmuch as the data are stored in a relatively casual and unconnected sequence in the file. The time used to search for and retrieve topological data is also governed by the way in which the data are structured for storage. A rational data structure will reduce the storage volume. Special techniques have therefore been developed for dividing and structuring data.

Generally, geometric data are stored in map sheets or other geographical units, but storing map sheet data in single sequential files lengthens the response time. This has resulted in some GISs employing indexing to speed up the searching process, and enabling current map sheets to appear on screen almost immediately. Indexing specifies locations, so data are divided into sections that are distributed in such a manner as to accelerate the search. For example, zooming focuses on data in those sections relevant to a selected area and ignores the rest of the data volume.

Hashing

The underlying concept for hashing is that a key is used to look up, in a table, all objects that share the key value, and thereby to be able to locate the data physically on a disk. Each cell section is assigned a number, which is listed in a table of pointers to storage locations (Figure 12.6). The cell section numbers, and hence the entries in the index table, may be calculated from Cartesian coordinates.

The following is an example of the use of ...