Previous Next

                                           163
SECTION 3.8                                                     Common Data Structures



appear before longer ones beginning with the same byte sequence. The encoding
of the keys is immaterial as long as it is self-consistent; keys are compared for
equality on a simple byte-by-byte basis.

The keys contained within the various nodes’ Names entries do not overlap; each
Names entry contains a single contiguous range of all the keys in the tree. In a leaf
node, the Limits entry specifies the least and greatest keys contained within the
node’s Names entry. In an intermediate node, it specifies the least and greatest
keys contained within the Names entries of any of that node’s descendants. The
value associated with a given key can thus be found by walking the tree in order,
searching for the leaf node whose Names entry contains that key.

Example 3.17 is an abbreviated outline, showing object numbers and nodes, of a
name tree that maps the names of all the chemical elements, from actinium to
zirconium, to their atomic numbers. Example 3.18 shows the representation of
this tree in a PDF file.

Example 3.17 Example of a name tree

      1: Root node
            2: Intermediate node: Actinium to Gold
                  5: Leaf node: Actinium = 25, … , Astatine = 31
                         25: Integer: 89
                         …
                         31: Integer: 85
                  …
                  11: Leaf node: Gadolinium = 56, … , Gold = 59
                         56: Integer: 64
                         …
                         59: Integer: 79
            3: Intermediate node: Hafnium to Protactinium
                  12: Leaf node: Hafnium = 60, … , Hydrogen = 65
                         60: Integer: 72
                         …
                         65: Integer: 1
                  …
                  19: Leaf node: Palladium = 92, … , Protactinium = 100
                         92: Integer: 46
                         …
                         100:Integer: 91
            4: Intermediate node: Radium to Zirconium
                  20: Leaf node: Radium = 101, … , Ruthenium = 107
                         101:Integer: 89

Previous Next