As explained in the Indexes page, the eXtremeDB Patricia Trie indexes can be used for optimal access of IP addresses and similar alphanumeric strings.
Searches on
patricia
indexes are performed using thepatricia
-specific search methods LongestMatch, ExactMatch, PrefixMatch and NextMatch.LongestMatch
The LongestMatch search locates the record whose index value has the longest match, i.e. has the greatest number of characters or bits starting from the right that match the key value. For example, consider a class Operators with string fields
prefix
andoperator
and apatricia
index on the fieldprefix
, and the following values:
prefix operator 01 ATT 020 BCC 025 TNT 03 ANC 0355 NCC 0355 UDC 045 WTC The LongestMatch search with a key value of
02456
would position the cursor at the object withprefix=025
andoperator=TNT
; with a key value of035567787
at the object withprefix=0355
andoperator=UDC
); and with a key value of03
at the object withprefix=0355
andoperator=UDC
as well. Notice that the cursor is positioned at the last record matching the key value. In order to walk through the result set to visit all records matching the key value, applications will use thenextMatch
function or method.ExactMatch
The ExactMatch search locates the first record whose index value exactly matches the key value supplied. If no exact matches are found
MCO_S_NOTFOUND
is returned. For example, using the above table: the ExactMatch search with the key value of02
would find the object withprefix=020
andoperator=BCC
, but the key value of024
would causeMCO_S_NOTFOUND
to be returned.PrefixMatch
The PrefixMatch search is similar to LongestMatch except that it finds the first object whose index matches the key, whereas LongestMatch returns the object with the longest (deepest) match. So using the above table: the PrefixMatch search with the key value of
02456
finds the object withprefix=025
andoperator=TNT
; the key value of035567787
finds the object withprefix=0355
andoperator=NCC
; and the key of value03
finds the object withprefix=03
andoperator=ANC
.NextMatch
The NextMatch search is used after the
cursor
is positioned within the result set, to walk through the result set to visit all records matching the key value. To traverse the database objects in order, applications can use the standardcursor
next or prev operations, but these functions are not constrained by the key value used to perform the initial search; so iteration could continue beyond the range specified in the key.Example search
Unlike other index compare functions that return <0, 0 or >0, the
patricia
-based compare function returns the number of the first different bit between the key and the object pointed to by thecursor
. This allows interrupting thecursor
traversal in a manner similar to the “standard” compare API. In addition, the application is able to refine the cursor traversal. For example consider a routing table containing the following values:128.1.1.0 128.1.1.10 128.1.1.20 128.1.2.0 128.1.2.10 128.1.3.0stored in a database class Nodes with a
patricia
index on an integer of bit array fieldipaddr
. Suppose the application is looking for the entire subnet128.1.1
.The search key value would be passed in as
10000000|00000001|00000001 binary or 8388865The PrefixMatch search called with this key value and length 24 (i.e. 24 bits), positions the cursor at the object with
ipaddr
equivalent to128.1.1.0
. Now the NextMatch function is called to advance to record128.1.1.10
and thepatricia
compare function returns the value28
which means that28
bits of the recordsipaddr
match the key value.Continuing: the
cursor
next operation advances to record128.1.1.20
and thepatricia
compare function returns27
; thencursor
next advances to record128.1.2.0
and thepatricia
compare function returns22
.At this point the application would conclude that it has left the region of interest since the key size is
24
bits and the mismatch was detected in the 22nd bit. In other words the key is no longer a prefix for the value in the object now pointed at by thecursor
.