# Index Searches in C#

> 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 `BTree`-based (including `Patricia`, `RTree`, `KDTree` 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
>             public String code;
>             public String name;
>         }

>         [Persistent]
>         class Employee
>         {
>             [Indexable(Type = Database.IndexType.BTree, Unique = true)] // Declare unique tree index by "name" field
>             public String name;

>             [References(typeof(Department))]
>             public 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, "name");
>         Employee 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 d = cursor2.Find(emp.dept);
>         Console.Write(d.name + " are:\n");
>         con.CommitTransaction();
>         cursor.Close();
>         cursor2.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)]
>             public String  name;

>             public 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);
>         // 1. Find the Employee object by name
>         Cursor<Employee> cursor = new Cursor<Employee>(con, "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` C# 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 will be stored in eXtremeDB database
>         class AreaCode
>         {
>             [Indexable(Type=Database.IndexType.Patricia)] // Declare patricia index by "areaCode" field
>             public String areaCode;

>             [Dimension(4)]
>             public 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");
>         foreach (AreaCode ac in cursor)
>         {
>             Console.WriteLine(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 C# 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");
>         if (cursor.Search(Operation.ExactMatch, strAreaCode))
>         {
>             Console.WriteLine("\tFound " + op + " for key " + strAreaCode);
>             do
>             {
>                 cursor.MoveNext();
>                 Console.WriteLine(cursor.Current.ToString());
>             } while (cursor.Search(Operation.NextMatch, strAreaCode));
>         }
>         else
>         {
>             Console.WriteLine("\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 `Operation.PrefixMatch` as the `Search()` operation. Likewise, substitute `Operation.BestMatch` for a "best match" search. Note that to advance the Cursor, the operation `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 `Neighbourhood`.

> 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` C# APIs, the SDK sample 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:

>         static int IterateRects(Cursor<Rect> cursor, bool reverseOrder)
>         {
>             int i = 0;

>             for (bool hasNext = reverseOrder ? cursor.MoveLast() : cursor.MoveFirst();
>             hasNext = reverseOrder ? cursor.MovePrev() : cursor.MoveNext())
>             {
>                 if (i++ < SHOW_FIRST)
>                 {
>                     Console.WriteLine("\t" + i + "." + cursor.Current);
>                 }
>             }
>             if (i > SHOW_FIRST)
>             {
>                 Console.WriteLine("\t...");
>             }
>             return i;
>         }

> Note that here the `Search()` method is not needed as the Cursor is simply positioned using the `MoveFirst()` or `MoveLast()` method depending on the value of flag `reverseOrder` and the sequential navigation of database objects is performed by calling method `MoveNext()` or `MovePrev()`.

> ### 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);
>         // Create cursor
>         cursor = new Cursor<Rect> (con, "square");
>         Console.WriteLine("\n\n\tSearch(Operation.Equals, '" + rect3 + "');");
>         if (cursor.Search(Operation.Equals, rect3.square))
>         {
>             i = IterateRects(cursor, false);
>             Console.WriteLine("\tFound " + i + " total rects");
>         }
>         cursor.Close();
>         con.CommitTransaction();

> To perform an "overlaps" search, we could use code like the above, simply substituting `Operation.Overlaps` as the `Search()` operation. Likewise, substitute `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 `Operation.Neighbourhood`.

> ## KD-Tree Index Search

> As explained in the Indexes and Cursors page, `kdtree` indexes are ideal for multi-dimensional key value searches. Searches on `kdtree` indexes are performed using the generated `_search()` function using a Query-By-Example approach to locate objects that match a given search condition.

> Please refer to the KDTree Index page for explanations and examples of how this `KDTree`-specific search works. To demonstrate use of the `KDTree` C# APIs, the SDK sample KDTree is provided. Code snippets from this sample are used below to illustrate Query-By-Example searches.

> Consider the following class definition which is the C# equivalent of the database schema presented in the KDTree Index page:

>         [Persistent] // store class in eXtremeDB database
>         [Index("idx", Type=Database.IndexType.KDTree, Keys=new string[]{"Year", "Milage",
>                 "Color", "Model", "Vendor", "Automatic", "AC", "Price"})]
>         public interface Car
>         {
>             string Vendor{get; set;}
>             string Model{get; set;}
>             string Color{get; set;}
>             uint Year{get; set;}
>             uint Milage{get; set;}
>             bool Automatic{get; set;}
>             bool AC{get; set;}
>             uint Price{get; set;}
>             [Dimension(2)]
>             string State{get; set;}
>         }

> To perform a Query-By-Example search, we temporarily insert a single "pattern object" if an exact match search, or two boundary "pattern objects" `from` and `till` to specify a range. Then we call the Cursor method `QueryByExample` and use the cursor methods `MoveNext()` or `MovePrev()` to advance through the result set. For example:

>         /* Use read-write transaction to store boundary patterns in the database */
>         con.StartTransaction(Database.TransactionType.ReadWrite);
>         Car from = con.Create<Car>();
>         Car till = con.Create<Car>();
>         from.Vendor = till.Vendor = "Ford";
>         till.Price = 30000;
>         from.Year = 2000;
>         till.Year = 2006;
>         till.Milage = 100000;
>         Console.WriteLine("*** Range query");
>         Console.WriteLine("From:");
>         PrintCar(from);
>         Console.WriteLine("Till:");
>         PrintCar(till);
>         Console.WriteLine("Results:");

>         Cursor<Car> cursor = new Cursor<Car>(con, "idx");
>         if (cursor.QueryByExample(from, till))
>         {
>             foreach (Car car in cursor)
>             {
>                 PrintCar(car);
>             }
>         }
>         cursor.Close();
>         con.RollbackTransaction();

> ## 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` C# 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` C# APIs, the SDK sample Hash 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
>             public int iIdx;

>             [Indexable(Type=Database.IndexType.Hashtable, Unique=false, InitSize=10000)] // Declare non-unique hash index
>             public 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;

>         con.StartTransaction(Database.TransactionType.ReadOnly);
>         cursor = new Cursor<Record>(con, "iIdx");
>         // Get found record - or not
>         rec = cursor.Find(findValue);
>         if (rec != null )  {
>             string[] array = rec.Consumers.ToArray();
>             Console.WriteLine("\tIndex " + rec.iIdx + " Series " + rec.iSeries + " Consumers no0 " + array.GetValue(0));
>         }
>         else
>         {
>             Console.WriteLine("\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:

>         int findValue = 10;
>         Record rec;

>         // Show all records with specified value in non-unique index
>         Console.WriteLine("\n\n\tSearch for records with iSeries == " + findValue);
>         con.StartTransaction(Database.TransactionType.ReadOnly);
>         cursor = new Cursor<Record>(con, "iSeries");
>         // Search for records with specified value for iSeries */
>         if (cursor.Search(Operation.Equals, findValue))
>         {
>             // Show all records in cursor
>             bool hasNext = cursor.MoveFirst();
>             for (i = 0; hasNext && i < nRecs; ++i)
>             {
>                 rec = cursor.Current;
>                 string[] array = rec.Consumers.ToArray();
>                 Console.WriteLine("\tIndex " + rec.iIdx + " Series " + rec.iSeries + " Consumers no0 " + array.GetValue(0));
>                 hasNext = cursor.MoveNext();
>             }
>         }
>         else
>         {
>             Console.WriteLine("\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
>             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);

>         Console.WriteLine("\n\tIterate through cursor with no search condition : ");
>         i = IterateRects(cursor, false);
>         Console.WriteLine("\tFound " + i + " total rects");
>         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.