# Index Searches in Java

> Search interfaces locate desired objects or groups of objects by unique identifier or by index. Exact match lookups by `unique` identifier (including `HashTable` and `autoid` ) using the Cursor method `find()` are extremely efficient for locating individual objects. eXtremeDB also offers a rich set of specialized indexes that employ `Cursors` to navigate a group of objects as an ordered result set with `tree`-based (including `patricia`, `rtree` and `trigram`) , or an unordered sequence of objects with `HashTable` indexes declared as `unique=false` or `List` indexes.

> # Find

> The Cursor method `find()` searches an index for an exact match. By definition, an exact match lookup on a unique index returns exactly one result or zero if no match is found. Note that an `autoid` is by definition unique. So an internally managed unique `HashTable` index is implemented for it and only the exact match `find()` method is appropriate for `autoid` object lookups.

> ## Autoid Lookup

> As explained in the Indexes and Cursors page, only "exact match" searches are possible for `autoid` indexes which are performed using the Cursor method `find()`. To demonstrate, consider the following schema:

>         @Persistent(autoid = true)
>         class Department
>         {
>             @Indexable(type=Database.IndexType.BTree, unique=true) // Declare unique tree index by "code" field
>             String code;
>             String name;
>         }

>         @Persistent()
>         class Employee
>         {
>             @Indexable(type=Database.IndexType.BTree, unique=true) // Declare unique tree index by "name" field
>             String name;
>             long dept;
>         }

> Note that a one-to-many relationship between Department and Employee objects can be implemented through the reference field `dept` of type `long` in class Employee. If each Employee object stores the `autoid` value of the Department object to which it belongs, the owner Department object could be quickly found with code like the following:

>         con.startTransaction(Database.TransactionType.ReadOnly);
>         // 1. Find the Employee object by name
>         Cursor<Employee> cursor = new Cursor<Employee>(con, Employee.class, "name");
>         Employee emp;
>         emp = cursor.find(search_name);

>         // 2. Find the Department object by its autoid and display the Department name
>         Cursor<Department> cursor2 = new Cursor<Department>(con, Department.class);
>         Department d = cursor2.find(emp1.dept);
>         System.out.println("\n\nFind " + search_name + "'s co-workers in " + d.name + " :\n");
>         con.commitTransaction();
>         cursor.close();

> Note that here the Cursor `cursor2` is instantiated on class Department without specifying an index, which means "use the class `autoid` index".

> # Search

> A `Cursor` is essentially an iterator over the collection of objects in a result set. For each non-unique index declared for a class a Cursor can be instantiated. The Cursor method `search()` positions it based on some value(s), and the `current()` method provides a handle to the database object at the current position. Most index types provide an ordered result set; `List`-based and non-unique `HashTable`-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 .

> ### Cursor Navigation

> After positioning a cursor with the `search()` method or one of the cursor positioning functions (`moveFirst(), moveLast(), moveNext()` or `movePrev()`), the `current()` method can be used to obtain a handle to the object in order to then use object interface methods.

> ## BTree Index Search

> To demonstrate a common `BTree` index search scenario, consider the following database class definition:

>         @Persistent()
>         class Employee
>         {
>             @Indexable(type=Database.IndexType.BTree, unique=true) // Declare unique tree index by "name" field
>             String name;
>             int dept_no;
>         }

> To lookup an Employee object by the `BTree` index `name`, we could use code like the following:

>         Employee emp;
>         String search_name = "William";

>         con.startTransaction(Database.TransactionType.ReadOnly);
>         Cursor<Employee> cursor = new Cursor<Employee>(con, Employee.class, "name");
>         emp = cursor.find(search_name);
>         con.commitTransaction();
>         cursor.close();

> ## Patricia Index Search

> As explained in the Indexes and Cursors page, the `Patricia` index can be declared `unique`; in the absence of the `unique` keyword it defaults to allowing duplicates.

> Searches on `Patricia` indexes are performed using the Cursor operations `ExactMatch`, `BestMatch`, `PrefixMatch` and `NextMatch`.

> Please refer to the Patricia Index page for explanations and examples of how these `Patricia`-specific search operations work. To demonstrate use of the `Patricia` Java APIs, the SDK sample Indexes_Patricia is provided. Code snippets from this sample are used below to illustrate the different types of `Patricia` index searches.

> Consider the class AreaCode with string fields like the following:

>         @Persistent
>         class AreaCode
>         {
>             @Indexable(type=Database.IndexType.Patricia) // Declare patricia index by "areaCode" field
>             String areaCode;

>             @Dimension(4)
>             String strAreaCode;
>         }

> ### Sequential search

> To sequentially list the contents of the database using the `Patricia` index `areaCode`, we could use code like the following:

>         con.startTransaction(Database.TransactionType.ReadOnly);
>         Cursor<AreaCode> cursor = new Cursor<AreaCode>(con, AreaCode.class, "areaCode");
>         for (AreaCode ac : cursor)
>         {
>             System.out.println(ac.toString());
>         }
>         cursor.close();
>         con.commitTransaction();

> Note that here the `search()` method is not needed as the `Cursor` is simply instantiated and the sequential navigation of database objects is performed by standard Java iteration of the `Cursor`.

> ### Exact Match, Prefix Match and Best Match searches

> To perform an "exact match" search, we could use code like the following:

>         con.startTransaction(Database.TransactionType.ReadOnly);
>         Cursor<AreaCode> cursor = new Cursor<AreaCode> (con, AreaCode.class, "areaCode");
>         if (cursor.search(Cursor.Operation.ExactMatch, strAreaCode))
>         {
>             System.out.println("\tFound " + op + " for key " + strAreaCode);
>             do
>             {
>                 System.out.println(cursor.next().toString());
>             } while (cursor.search(Cursor.Operation.NextMatch, strAreaCode));
>         }
>         else
>         {
>             System.out.println("\t" + op + " not found for key " + strAreaCode);
>         }
>         cursor.close();
>         con.commitTransaction();

> To perform a "prefix match" search, we could use code like the above, simply substituting `Cursor.Operation.PrefixMatch` as the `search()` operation. Likewise, substitute `Cursor.Operation.BestMatch` for a "best match" search. Note that to advance the Cursor, the operation `Cursor.Operation.NextMatch` is used.

> ## RTree Index Search

> As explained in the Indexes and Cursors page, the `RTree` index is commonly used to speed spatial searches. Searches on `RTree` indexes are performed using the Cursor method `search()` with one of the four operations `Equals, Overlaps, Contains` or `Neighborhood`.

> Please refer to the RTree Index page for explanations and examples of how these `RTree`-specific search operations work. To demonstrate use of the `RTree` Java APIs, the SDK sample Indexes_RTree is provided. Code snippets from this sample are used below to illustrate the different types of `RTree` index searches.

> Consider the class Rect with a definition like the following:

>         @Persistent(list=true) // Store class in eXtremeDB database, declare list index
>         class Rect
>         {
>             @Dimension(4)
>             @Indexable(type=Database.IndexType.RTree) // Declare rtree index on "square" field
>             public short[] square;
>         }

> ### Sequential search

> To sequentially list the contents of the `Cursor` using the `RTree` index, we could use code like the following:

>         // Print out objects in direct or reverse order
>         static int iterateRects(Cursor<Rect> cursor, boolean reverse_order)
>         {
>             int i = 0;

>             for (Rect rect = (reverse_order) ? cursor.last() : cursor.first();
>             rect != null;
>             rect = (reverse_order) ? cursor.prev() : cursor.next())
>             {
>                 if (i++ < SHOW_FIRST)
>                 {
>                     System.out.println("\t" + i + "." + rect);
>                 }
>             }
>             if (i > SHOW_FIRST)
>             {
>                 System.out.println("\t...");
>             }
>             return i;
>         }

> Note that here the `search()` method is not needed as the Cursor is simply positioned using the `first()` or `last()` method depending on the value of flag `reverse_order` and the sequential navigation of database objects is performed by calling method `next()` or `prev()`.

> ### Exact Match, Overlaps, Contains and Neighbourhood searches

> To perform an "exact match" search, we use operation `Equals` with code like the following:

>         con.startTransaction(Database.TransactionType.ReadWrite);
>         cursor = new Cursor<Rect> (con, Rect.class, "square");
>         System.out.println("\n\n\tSearch(Operation.Equals, '" + rect3 + "');");
>         if (cursor.search(Cursor.Operation.Equals, rect3.square))
>         {
>             i = iterateRects(cursor, false);
>             System.out.println("\tFound " + i + " rect(s)");
>         }
>         cursor.close();
>         con.commitTransaction();

> To perform an "overlaps" search, we could use code like the above, simply substituting `Cursor.Operation.Overlaps` as the `search()` operation. Likewise, substitute `Cursor.Operation.Contains` for a "contains" search. To list the entire contents of the Rect class in order of each object's distance from a point, we specify the point coordinates in `rect3.square` and use `search()` operation `Cursor.Operation.Neighbourhood`.

> ## Trigram Index Search

> As explained in the Indexes and Cursors page, `Trigram` indexes are ideal for text searches when the exact spelling of the target object is not precisely known.

> Please refer to the Trigram Index page for explanations and examples of how these `Trigram`-specific search operations work. To demonstrate use of the `Trigram` Java APIs, the SDK sample Indexes_Trigram is provided. Code snippets from this sample are used below to illustrate the different types of `Trigram` index searches.

> Consider the class TrigramObj with a definition like the following:

>         @Persistent
>         class TrigrmObj
>         {
>             @Indexable(type=Database.IndexType.Trigram)
>             String carid;
>         }

> To perform a `search()` using a `Trigram` index we might use code like the following:

>         String[] search_pattern = { "768", " 77", "4pi", "8cc", "7u7", " 77a474ko" };

>         for (String ptrn : search_pattern)
>         {
>             con.startTransaction(Database.TransactionType.ReadOnly);
>             cursor = new Cursor<TrigrmObj>(con, TrigrmObj.class, "carid");
>             System.out.println("\nObjects with pattern (" + ptrn + "):");
>             if (cursor.search(Cursor.Operation.Contains, ptrn))
>             {
>                 for (TrigrmObj o : cursor)
>                 {
>                     System.out.println("\t(" + o.carid + ") ");
>                 }
>             }
>             cursor.close();
>             con.rollbackTransaction();
>         }

> ## HashTable Index Search

> As explained in the Indexes and Cursors page, `HashTable` indexes are generally used for efficient object lookups. Also, as explained in the Search section above, a `HashTable` index declared `unique=false` allows Cursor navigation in sequential order (first to last, or last to first) over the unordered list of objects of a class. To demonstrate use of the `HashTable` Java APIs, the SDK sample Indexes_HashTable is provided. Code snippets from this sample are used below.

> Consider the database schema presented in the Indexes and Cursors page:

>         @Persistent
>         class Record
>         {
>             @Indexable(type=Database.IndexType.Hashtable, unique=true, initSize=10000) // Declare unique hash index
>             int iIdx;

>             @Indexable(type=Database.IndexType.Hashtable, unique=false, initSize=10000) // Declare non-unique hash index
>             int iSeries;
>         }

> The unique index `iIdx` in this class can be used only for exact lookups with Cursor method `find()`. For example:

>         int findValue = 10;
>         Record rec;

>         // Find a specific value in unique index
>         System.out.println("\n\n\tFind record with index == " + findValue);

>         Connection con = new Connection(db);
>         con.startTransaction(Database.TransactionType.ReadOnly);
>         // Open the cursor
>         Cursor cursor = new Cursor<Record>(con, Record.class, "iIdx");
>         rec = cursor.find(findValue);
>         if ( rec != null )
>         {
>             System.out.println("\tIndex " + rec.iIdx + " Series " + rec.iSeries);
>         }
>         else
>         {
>             System.out.println("\tnot found");
>         }
>         cursor.close();
>         con.rollbackTransaction();

> The following code snippet demonstrates how to use a non-unique `HashTable` index `iSeries` to search for all objects having a specified value:

>         con.startTransaction(Database.TransactionType.ReadOnly);
>         cursor = new Cursor<Record>(con, Record.class, "iSeries");
>         // Search for records with specified value for iSeries */
>         if (cursor.search(Cursor.Operation.Equals, findValue))
>         {
>             // Show all records in cursor
>             rec = cursor.first();
>             for (i = 0; i < nRecs && rec != null; ++i)
>             {
>                 System.out.println("\tIndex " + rec.iIdx + " Series " + rec.iSeries);
>                 rec = cursor.next();
>             }
>         }
>         else
>         {
>             System.out.println("\tno records found.");
>         }
>         cursor.close();
>         con.rollbackTransaction();

> ## List Index Search

> As explained in the Indexes and Cursors page, the `List` index, like a non-unique `HashTable`, allows navigation in sequential order (first to last, or last to first) over the unordered list of objects of a class.

> Consider the class Rect used above for the `RTree` example:

>         @Persistent(list=true) // Store class in eXtremeDB database, declare list index
>         class Rect
>         {
>             @Dimension(4)
>             @Indexable(type=Database.IndexType.RTree) // Declare rtree index on "square" field
>             public short[] square;
>         }

> Note the `@Persistent(list=true)` annotation. This causes a `List` index to be maintained internally as a non-unique `HashTable` index).

> ### Sequential search

> To sequentially list the contents of the `Cursor` using the `List` index, we could use code like the following:

>         con.StartTransaction(Database.TransactionType.ReadWrite);
>         // Create List cursor
>         Cursor cursor = new Cursor<Rect> (con, Rect.class, "square");

>         System.out.println("\n\tIterate through cursor with no search condition : ");
>         i = iterateRects(cursor, false);
>         System.out.println("\tFound " + i + " rect(s)");
>         cursor.close();
>         con.rollbackTransaction();

> Note that here the Cursor is instantiated on class Rect without specifying an index, which means use the class `List` index. Then method `iterateRects()` is called to perform the sequential navigation of database objects as above in the `RTree` example .