Indexes - negue/LiteDB GitHub Wiki

LiteDB improves search performance by using indices 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.

IndexOptions

LiteDB has some options that you can use when you are creating a new index. These options can't be modified after the index is created. If an index needs to be altered, LiteDB drops the current index and creates a new one.

  • Unique - Defines an index that has only unique values.
  • IgnoreCase - Convert field value to lower case. (String only)
  • RemoveAccents - Remove all accents on field value (áéíóú => aeiou) (String only)
  • TrimWhitespace - Apply String.Trim() on field value. (String only)
  • EmptyStringToNull - If field value are empty convert to BsonValue.Null. (String only)

Note: a change to an index value does not effect the indexed document's field value. These rules are applied only to the value stored in the index.

EnsureIndex()

Indices are created via LiteCollection.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. For performance reasons, this method checks only if the index exists and no index options have changed.

Indices 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)

Limitations

  • Index values must have less than 512 bytes (after BSON serialization)
  • Max of 16 indexes per collections - including the _id primary key
  • [BsonIndex] is not supported in embedded documents