Indexes

LiteDB improves search performance by using indexes on document fields. Each index stores the value of a specific field ordered by the value (and type) of the field. Without an index, LiteDB must execute a query using a full document scan. Full document scans are inefficient because LiteDB must deserialize all documents to test each one by one.

Index Implementation

LiteDB uses the a simple index solution: Skip Lists. Skip lists are double linked sorted list with up to 32 levels. Skip lists are super easy to implement (only 15 lines of code) and statistically balanced. The results are great: insert and find results has an average of O(ln n) = 1 milion of documents = 13 steps. If you want to know more about skip lists, see this great video.

Documents are schema-less, even if they are in the same collection. So, you can create an index on a field that can be one type in one document and another type in another document. When you have a field with different types, LiteDB compares only the types. Each type has an order:

BSON Type	Order
MinValue	1
Null	2
Int32, Int64, Double	3
String	4
Document	5
Array	6
Binary	7
ObjectId	8
Guid	9
Boolean	10
DateTime	11
MaxValue	12

Numbers (Int32, Int64 or Double) have the same order. If you mix these number types in the same document field, LiteDB will convert them to Double when comparing.

EnsureIndex()

Indexes are created via EnsureIndex. This instance method ensures an index: create the index if it does not exist, re-creates if the index options are different from the existing index, or does nothing if the index is unchanged.

Another way to ensure the creation of an index is to use the [BsonIndex] class attribute. This attribute will be read and will run EnsureIndex the first time you query.

Indexes are identified by document field name. LiteDB only supports 1 field per index, but this field can be any BSON type, even an embedded document.

{
    _id: 1,
    Address:
    {
        Street: "Av. Protasio Alves, 1331",
        City: "Porto Alegre",
        Country: "Brazil"
    }
}

You can use EnsureIndex("Address") to create an index to all Address embedded document
Or EnsureIndex("Address.Street") to create an index on Street using dotted notation
Indices are executed as BsonDocument fields. If you are using a custom ResolvePropertyName or [BsonField] attribute, you must use your document field name and not the property name. See Object Mapping.
You can use a lambda expression to define an index field in a strongly typed collection: EnsureIndex(x => x.Name)
You can define your index in fluent mapping api. See Object Mapping

MultiKey Index

When you create an index in a array type field, all values are included on index keys and you can search for any value.

public class Customer
{
    public int Id { get; set; }
    public string Name { get; set; }
    public string[] Phones { get; set; }
}

var customers = db.GetCollection<Customer>("customers");

customers.Insert(new Customer { Name = "John", Phones = new string[] { "1", "2", "5" });
customers.Insert(new Customer { Name = "Doe", Phones = new string[] { "1", "8" });

var result = customers.Query(x => x.Phones.Contains("1")); // returns both documents