# eXtremeDB Indexes

> eXtremeDB supports hash indexes, and tree indexes of the following types: `tree` (b-tree), `patricia` (Patricia Trie), `rtree` (R-tree spatial), `kdtree` (kd-tree multi-dimensional), `trigram` (text substring) and `user-defined` (“custom”). `Hash` and `unique tree` indexes can also be used to uniquely identify objects in the database. Also, specialized hash indexes of type `oid` and `autoid` are provided as unique object identifiers. Unlike oids and autoids, however, `hash` and `tree` index values are only required to be unique within a class; the `nonunique` declaration can be used to allow duplicate values for `hash` or `tree` indexes.

> (See the Indexes and Cursors page for detailed descriptions and implementation details for each of the index types described below.)

> ## Tree Index

> An eXtremeDB `tree` index is a tree-like structure in the application’s memory that contains a collection of keys. A key can be simple (based on a single field) or compound (containing more than one field). The tree-index stores the keys in sorted order. In order to support sorting, the tree-index must have a compare function. Regardless of the key type (simple or compound), the compare function must be able to compare two keys and determine whether the first key is less than (compare returns -1), equal to (0) or greater than (1) the second key. The tree-index algorithm sorts the keys based on this comparison.

> > ### Search Methods

> > Search APIs are generated by the `mcocomp` schema compiler to locate desired objects or groups of objects by unique identifier or by index. While exact match lookups by unique identifier ( `unique tree` or `hash` index, `oid` and `autoid` ) using the generated `_find()` functions are extremely efficient for locating individual objects, the rich set of specialized indexes mentioned above employ cursors to navigate a group of objects as an ordered or unordered result set.

> > ### Find

> > By definition, an exact match lookup on a unique index returns exactly one result or zero if no match is found. So for C and C++ applications, the mcocomp schema compiler generates a `_find()` function for each unique index. Java and C# applications use the Cursor.Find() method.

> > ### Search

> > A cursor is essentially an iterator over the collection of objects in a result set. For each index declared for a class in the schema definition, the DDL compiler generates functions to instantiate a cursor, position it based on some value(s), and obtain a handle to the database object from the cursor. `List` and `nonunique` hash-based cursors allow navigation in sequential order (first to last, or last to first), though the order of the sequence is not defined; it is simply a mechanism to iterate over the unordered list of objects of a class.

> > For C or C++ applications, mcocomp generates a `_search()` function for each `nonunique` index in the schema. Java and C# applications use the Cursor.Search() method. The search function is used whenever it is necessary to establish:

> > - a starting position in a sorted list with a known starting value and optionally retrieve subsequent results in ascending or descending sorted order.
> > - a starting position in a sorted list when only part of the starting value is known, find the closest match, and optionally retrieve subsequent results in ascending or descending sorted order.
> > - a starting position as above, iterate over the sorted list in ascending or descending sorted order until a lower/upper bound is reached, using the _compare() method to determine when the range limit is reached.
> > - a starting position with a known starting value, iterate over the list to retrieve each duplicate, using the `_compare()` method to determine when the last duplicate was retrieved.

> > ### Pattern Search

> > eXtremeDB also supports "wild card" pattern matching ability. This is the capability to search tree index entries matching patterns specified with wild card characters for single character and multiple character matches. By default, the question mark “?” will match any single character in the specified position within the pattern, and the asterisk “*” will match any combination of characters (including no characters) in that position. If a match on the characters “?” or “*” is desired, the wild card characters themselves can be modified by specifying different characters in the pattern search policy (see below).

> > For example, “G*e*” would return “Graves” and “Gorine”, while “Gr?ve*” would match “Graves”, “Grove”, “Grover” and so on... In this example, ‘*’ matches zero, one, or more characters, while ‘?’ matches exactly one character. Further, the pattern “G*E*” would match all uppercase entries like “GRAVES”, “GORINE”. However, because the standard compare functions used to match index values with search keys use case-sensitive compare functions, the case specified in the search pattern will affect the search results.

> > ### Key-Value-Inclusive Indexes

> > eXtremeDB allows a “key-value-inclusive” or “cache-oblivious” implementation for in-memory (`transient`) database classes. This expedites access for certain access patterns. In particular experiments with very large B-Tree indexes show significant performance improvements. Also, the trigram index (described below) is implemented via the “key-value-inclusive” tree because it is much more efficient to keep 3 extra bytes (trigrams) on the index page than to simply store an 8-byte object address which requires further access steps.

> > ### Covering Indexes

> > If all the fields requested in an index search are available in the index tree node, then the runtime doesn't have to look up the object covered by the index again. This can significantly increase the performance of searches. Since all the requested fields are available within the index, the index is called a “covering index”. In addition, a “covering” index can be also declared inclusive to leverage CPU cache usage.

> ## Patricia Trie Index

> The eXtremeDB `Patricia` index uses a Patricia `trie` structure that is based on a radix tree using a radix of two. The term "trie" is derived from the word "retrieval". Patricia stands for "Practical Algorithm to Retrieve Information Coded as Alphanumeric”. This algorithm is optimized to perform quick IP address prefix matching for IP subnet, network or routing table lookups. So Patricia Trie indexes are particularly useful for network and telecommunications applications.

> A Patricia index can be declared over scalar and boolean data types as well as arrays and vectors of those types. In fact, the boolean data type was introduced to facilitate Patricia index implementation where bit arrays are used to store IP addresses.

> ## RTree Index

> `RTree` indexes are commonly used to speed spatial searches, for example, find the rectangle that contains this point, find all rectangles that overlap this rectangle, or find all rectangles in the neighborhood of this point.

> All manner of shapes can be stored and searched with the `rtree` index. For example, a point is represented as a rectangle with width and height = 1 and a line that has starting and ending coordinates of 15, 844 and 0, 3647 is stored as rectangle with its upper left corner at 15, 844 and its lower right corner at 0, 3647.

> To determine if two lines intersect, or if a point is within a given area (described by a circle, rectangle, etc.), an `rtree` search is performed to find all overlapping rectangles.

> ## Kd-Tree Index

> A `kdtree` is a data structure for organizing points in a k-dimensional space. `kdtrees` are a useful data structure for several applications, such as lookups that involve a multidimensional search key. The `kdtree` is a binary tree in which every node is a k-dimensional point. Every non-leaf node generates a splitting hyperplane that divides the space into two subspaces. Points left of the hyperplane represent the left sub-tree of that node and the points right of the hyperplane represent the right sub-tree. The hyperplane direction is chosen in the following way: every node split to sub-trees is associated with one of the k-dimensions, such that the hyperplane is perpendicular to that dimension vector.

> The `kdtree` uses a Query-By-Example approach to locate objects that match a given search condition. The application creates pattern object(s) and assigns values to the fields that are included in the search criteria. The `kdtree` supports simple exact matches as well as range lookups. In the latter case, two pattern objects will be specified: one for the lower and one for the upper bounds of the search condition. If a field value is defined only for one boundary, it is considered an open interval that corresponds to a greater-than-or-equal-to or less-than-or-equal-to search condition.

> ## Trigram Index

> Trigram search is a method of searching for text when the exact syntax or spelling of the target object is not precisely known. It finds objects which match the maximum number of three-character strings in the entered search terms, i.e. near matches. A classical B-Tree index allows exact match queries (eg. x='qqq'), range queries (eg. “x >= 10 and x <= 100”) and prefix match queries (eg. “x >= 'abc’).

> However, for more complex regular expressions like “%xyz%” a B-Tree index would require a sequential search, which is significantly slower. In this case a trigram index can be ideal.

> The idea of `trigram` index is rather simple. Assume that we have a string key 'qwerty'. The string is split into trigrams: sequences of three subsequent characters: "qwe", "wer", "ert", "rty". These trigrams are stored in a normal B-Tree index. Now consider a query looking for the substring "wert". The query condition is also split into trigrams: "wer" and "ert". The search then is looking for these trigrams in the index. The result of the lookup is two lists of objects -- so called inverse lists. The next step is to join these lists: i.e. to find objects which are present in both lists.

> ## OID

> An eXtremeDB `oid` is a unique object identifier which is implemented internally as a unique hash index. Generally, an `oid` is a user-defined structure which has fixed-length fields corresponding to identifying characteristics of a principle database class. C and C++ applications can use `oids` to quickly retrieve the object it identifies.

> ## Autoid

> An `autoid` is similar to `oid` in that it is a unique object identifier implemented internally as a unique hash index. However it differs in that its value is determined by the eXtremeDB runtime, and the value is unique for the class, not the entire database. Autoids are 8-byte signed integer values which means that the value can be incremented every microsecond for nearly 300,000 years without overflowing.

> ## LIST

> A sequential navigation method is available for unordered lists of objects by specifying a `list` index. This allows applications to iterate over the objects of a class without regard to any particular order.