Database Reference
In-Depth Information
5.2 Trees
5.2.1
Tries
A
trie
is a multi-way tree specifically designed for indexing strings in
main memory. Given a set of strings
S
, the trie consists of one path
per distinct string
s
where each node in the path
corresponds to each character in
s
. Strings with the same prefixes share
the same paths. The leaf nodes of the paths store pointers to the actual
data (string identifiers, pointers to the location of the strings in a text
document, the table/column/row in a relational database, etc.). For
example, part of the trie corresponding to the strings of Table 5.1 is
shown in Figure 5.1. For static data, it is possible to compress a trie by
merging multiple nodes of the trie into a single node (using multiple
characters as the label of that node). This results in a Patricia trie (an
example is shown in Figure 5.2).
∈
S
, of length
|
s
|
c
i
o
l
u
f
h
e
o
n
n
a
n
u
n
i
l
e
d
o
d
u
t
e
p
t
i
c
n
e
d
d
r
o
e
...
p
f
...
Fig. 5.1 The trie for the strings in Table 5.1.
child
f
inter
...
eed
o
und
od
und
Fig. 5.2 The Patricia trie corresponding to part of the trie of Figure 5.1.
