ToC path:

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.