Soups

Soup Indexes

A soup index is based on the value of a particular slot and allows quick lookup for entries based on that slot value. Indexes also provide sorting capabilities. For example, if a soup is indexed using a name slot that contains a text string, entries can be accessed in a sorted (alphabetical) order on that string.

FIGURE 9.3 : Structure of an index.


An index is like a binary tree with key values in nodes of the tree. Searching for a particular key value is done by starting at the root node, and then comparing the search key with the value stored in the node. If the key is less, searching continues at the left child; if the key is greater, searching continues at the right child. Although indexes are slightly more complex than this (they are more like a B-tree data structure where there are more than two children for each node), the concept remains essentially the same. FIGURE 9.3 shows a typical index example.

Notice in the index in FIGURE 9.3 that the nodes at the leaf of the tree reference the actual entries in the soup and contain forward and backward pointers. This enables traversal to the next and previous node in index order.

Although indexes on the Newton aren't implemented using this exact data structure, the concept is similar.


An online version of Programming for the Newton using Macintosh, 2nd ed. ©1996, 1994, Julie McKeehan and Neil Rhodes.

Last modified: 1 DEC 1996