One of the first decisions in designing a server is what persistent storage structures to use. This section discusses how we organized storage structures for the grid example. There are numerous ways to organized storage. The primary decision is where to store the information about each item on the grid. We first discuss the implemented design and then present a couple alternatives.
We chose a relational database approach to organizing the data. Recall from the introduction that each item has a short string name and a coordinates on the grid. Each item is stored in a record. All item records are stored in a single file. Items can be retrieved using their record ID or by scanning the file.
To improve performance of lookups, we use two indexes. To support name lookups, we use a B+-tree index mapping item names to record IDs. To support lookups on location, we use an R*-tree mapping an item's coordinates to its record ID.
All files and indexes must be located on a volume. For the grid example, only one volume is used. This volume is located on a device, the name of which is specified with a configuration option. When the server starts, it must locate the file and indexes for the grid. To support this, the IDs of the file and indexes are stored in the root index of the volume.
This design has these desirable properties:
One alternative design is to store the item information in a B+-tree index. The item name is the key and coordinates are the data associated with the key.
This design has some problems. First, the R*-tree index would then map to names, making spatial lookups awkward. Second, if items are enlarged to hold more data, they may no longer fit within the size limitation (1-page) of index entries. Third, to updating the location of an item would mean removing it from the index and reinserting it, due to a lack of facilities for updating index entries.
Another alternative design is to treat the grid as a 2-D array of items and store the entire grid in one large record. This very efficient for densely populated grids, but is wasteful for sparse ones. It would also not support multiple items per location. Worse yet, the granularity of locking is the entire grid.