Volante : Volante Developer's Guide : B-Tree index (regular and thick index)

An entry in a B-Tree index consists of a key and a value. Value is a persistent object (implementing IPersistent interface).

Values are sorted by a key which allows quickly finding value by its key, all values within a given key range or enumerating values in the sort order of the key.

The key can be any of the standard .NET types: byte, int, string, DateTime, Guid etc. Sort order is the natural sort order for a given type.

When the key is a string, sorting is done with String.CompareTo().

Index can be unique (doesn't allow duplicate keys) or non-unique (allows duplicate keys).

A thick index is optimized for the case of many duplicte keys (it's a non-unique index by definition).

Index implements IIndex interface, which derives from IGenericIndex interface.

Key class

Many index functions take objects of class Key as an argument. Key class represents type and value of the index key. In many cases you can just use the raw value for the key and it'll be implicitly converted to the proper Key object. There are cases where you need to explicitly provide Key object.

Volante supports searches for inclusive and exclusive ranges. For example, if the index key is an integer and we've inserted objects with keys 1, 2, 3, 4, 5, a search for objects in inclusive range (2,4) will return objects whose key is 2, 3 or 4. If the range is in exclusive (2,4) range(on both sides), the search will return only objects whose key is 3.

The inclusivity/exclusivity is encoded in the Key object. When doing a range search, we provide the Key for the lower and upper range. Either key can be inclusive or exclusive so we have 4 possibilities.

To create a Key marked as exclusive you have to use the 2 argument constructor and pass false for the second argument which is of type bool and indicates inclusivity.

Key objects created with 1 argument constructor, including those created implicitly, are inclusive.

Another case where you need to explicitly use Key constructor is to disambiguate between integer types. If you have an index whose key is e.g. of type short, if you create a key with integer constant like var k = new Key(5), it'll create a Key with type int, which won't be compatible with your index. The right way to create a Key with a specific integer type is to force the right constructor with a cast: var k = new Key((short)5).

Creating an index

To create an index use IDatabase.CreateIndex<K, V>(IndexType indexType) method. IndexType is an enum that can be IndexType.Unique or IndexType.NonUnique.

K is type of the key, V is type of the value.

The result is an object implementing IIndex<K,V> interface. This object is used for all operations on the index.

Thick index is a more efficient implementation in the case of many duplicate keys. To create a thick index use IDatabase.CreateThickIndex<K, V>() method. It also returns IIndex<K,V> interface.

Inserting objects into an index

To insert an object with a given key, you have several options:

• bool Put(Key key, V obj)
• bool Put(K key, V obj)
• V Set(Key key, V obj)
• V Set(K key, V obj)
• V this[K key] { set; }

You can either provide the Key objects explicitly or the vale of the index type (in which case the Key will be created implicitly).

Put() adds a new object to the index, Set() associates an object with a given key. V this[K key] { set; } is equivalent to Set().

In a unique index, if an object with a given key already exists:

• Put() returns false and does not add the object to the index
• Set() will associate new object with the key (i.e. will overwrite the value) and return the old object associated with the key

If the key doesn't exist, the effect of Put() and Set() is the same.

In a non-unique index, if an object with a given key already exists:

• Put() will add another object with the key
• Set() will overwrite the object with this key, i.e. old object will be removed. If there is more than one object with this key, an exception will be thrown.

If the key doesn't exist, the effect is the same.

Removing objects from the index

To remove an object from non-unique index, you can use:

• void Remove(Key key, V obj)
• void Remove(K key, V obj)

Notice that you have to provide object to be removed to disambiguate between (possibly) many objects with the same key.

To remove an object from unique index you can additionally use:

• V Remove(Key key)
• V RemoveKey(K key)

Since there's at most one object with a given key, we only need the key to uniquely identify the object. Calling those methods on non-unique index will throw an exception.

Calling any of the above functions with a key that doesn't exist in the index will throw an exception.

What if you want to remove all objects with a given key from non-unique index? It's easy:

IPersistent[] objs = index.Get(key,key);
foreach (var obj in objs) {
    index.Remove(key, obj);
}

Retrieving objects by key

To retrieve an object by key:

• V Get(Key key)
• V Get(K key)
• V this[K key] { get; }

If you use Get(Key key), the key object should be inclusive.

If the value with a given key is not found the return value is null. If there is more than one value with a given key, a DatabaseException exception with DatabaseException.Code equal to DatabaseException.ErrorCode.KEY_NOT_UNIQUE is thrown.

Retrieving objects within a key range

There is a number of functions that return the values for keys within a given key range:

• V[] Get(Key from, Key till)
• V[] Get(K from, K till)
• V[] this[K from, K till] { get; }

Get(Key fro, Key till allows specifying either limit of the range as inclusive or exclusive by creating either inclusive or exclusive Key object. The other 2 functions use inclusive range.

Instead of getting an array of objects, you can obtain an enumerator for traversing the results:

• IEnumerator<V> GetEnumerator(Key from, Key till, IterationOrder order)
• IEnumerator<V> GetEnumerator(Key from, Key till)
• IEnumerator<V> GetEnumerator(K from, K till, IterationOrder order)
• IEnumerator<V> GetEnumerator(K from, K till)

An enumerator that can be explicitly traversed with IEnumerator.MoveNext() and its current value can be accessed with IEnumerator.Current. Iteration order can be specified as IterationOrder.AscentOrder (from low values to high values, the default value if not provided) or IterationOrder.DescentOrder.

You can also obtain enumerable object, which can be used in foreach loops:

• IEnumerable<V> Range(Key from, Key till, IterationOrder order)
• IEnumerable<V> Range(Key from, Key till)
• IEnumerable<V> Range(K from, K till, IterationOrder order)
• IEnumerable<V> Range(K from, K till)
• IEnumerable<V> Reverse()

Reverse() returns all elements sorted in descending order.

There's also functionality to enumerate both keys and values:

• IDictionaryEnumerator GetDictionaryEnumerator(Key from, Key till, IterationOrder order)
• IDictionaryEnumerator GetDictionaryEnumerator()

Changing the index (by adding/removing/changing values) invalidates IEnumerator and IEnumerable, so you can't use those values to delete them from the index. Modifying the index while iterating will throw an exception.

Prefix search

If the key is a string, we can ask for all values whose key starts with a given prefix:

• V[] GetPrefix(string prefix)
• IEnumerator GetEnumerator(string prefix)
• IEnumerable StartsWith(string prefix)

We can also ask for all objects whose key is a prefix of a given word with V[] PrefixSearch(string word).

Calling those functions on an index whose key is not a string will throw an exception.

Misc operations

You can get number of objects in the index with int Count property.

You can get type of the key with Type KeyType property.

V[] ToArray() returns all objects in the index as an array. It's inefficient for indexes with a large number of objects.

← indexes  •  field index →

---

Volante is maintained by Krzysztof Kowalczyk