SECTION 3.8
163
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.
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