As explained in the Indexes page, the eXtremeDB Patricia Trie indexes can be used for optimal access of IP addresses and similar alphanumeric strings.
patriciaindexes are performed using the
patricia-specific search methods LongestMatch, ExactMatch, PrefixMatch and NextMatch.
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
patriciaindex on the field
prefix, 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
02456would position the cursor at the object with
operator=TNT; with a key value of
035567787at the object with
operator=UDC); and with a key value of
03at the object with
operator=UDCas 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 the
nextMatchfunction or method.
The ExactMatch search locates the first record whose index value exactly matches the key value supplied. If no exact matches are found
MCO_S_NOTFOUNDis returned. For example, using the above table: the ExactMatch search with the key value of
02would find the object with
operator=BCC, but the key value of
MCO_S_NOTFOUNDto be returned.
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
02456finds the object with
operator=TNT; the key value of
035567787finds the object with
operator=NCC; and the key of value
03finds the object with
The NextMatch search is used after the
cursoris 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 standard
cursornext 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.
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 the
cursor. This allows interrupting the
cursortraversal 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:188.8.131.52 184.108.40.206 220.127.116.11 18.104.22.168 22.214.171.124 126.96.36.199
stored in a database class Nodes with a
patriciaindex on an integer of bit array field
ipaddr. Suppose the application is looking for the entire subnet
The search key value would be passed in as10000000|00000001|00000001 binary or 8388865
The PrefixMatch search called with this key value and length 24 (i.e. 24 bits), positions the cursor at the object with
188.8.131.52. Now the NextMatch function is called to advance to record
patriciacompare function returns the value
28which means that
28bits of the records
ipaddrmatch the key value.
cursornext operation advances to record
patriciacompare function returns
cursornext advances to record
patriciacompare function returns
At this point the application would conclude that it has left the region of interest since the key size is
24bits 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 the