Patricia trie Indexes

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 the patricia-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 and operator and a patricia index 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 02456 would position the cursor at the object with prefix=025 and operator=TNT; with a key value of 035567787 at the object with prefix=0355 and operator=UDC); and with a key value of 03 at the object with prefix=0355 and operator=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 the nextMatch 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 of 02 would find the object with prefix=020 and operator=BCC, but the key value of 024 would cause MCO_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 with prefix=025 and operator=TNT; the key value of 035567787 finds the object with prefix=0355 and operator=NCC; and the key of value 03 finds the object with prefix=03 and operator=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 standard cursor 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 the cursor. This allows interrupting the cursor 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.0
     

stored in a database class Nodes with a patricia index on an integer of bit array field ipaddr. Suppose the application is looking for the entire subnet 128.1.1.

The search key value would be passed in as

 
    10000000|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 ipaddr equivalent to 128.1.1.0. Now the NextMatch function is called to advance to record 128.1.1.10 and the patricia compare function returns the value 28 which means that 28 bits of the records ipaddr match the key value.

Continuing: the cursor next operation advances to record 128.1.1.20 and the patricia compare function returns 27; then cursor next advances to record 128.1.2.0 and the patricia compare function returns 22.

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 the cursor.

 

---