# 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`.