  Share this Page URL   11.11 Memory Allocation in Compressed
Schemes 261 at all lengths that binary search will visit in a
search for P. This adds only a logarithmic number of markers.
For a prefix of length 32, markers are needed only at lengths
16, 24, 28, and 30. Unfortunately, the algorithm is still
incorrect. While markers lead to potentially longer prefixes,
they can also cause search to follow false leads. Consider a
search for an address D whose first three bits are 100 in part
(B) of Figure 11.18. Since the median table contains 10, search
in the middle hash table results in a match. This forces the
algorithm to search in the third hash table for 100 and to fail.
But the correct best matching prefix is at the first hash table
-- i.e., P4 = 1*. Markers can cause the search to go off on a
wild goose chase! On the other hand, a backtracking search of
the left half would result in linear time. To ensure logarithmic
time, each marker node M contains a variable M.bmp, where M.bmp
is the longest prefix tha