BPlusTree 2.0 Changes Part 2 – Enumerate Ranges and First/Last

Continued from: Part 1 – Interface Changes

Enumerating Ranges
I’ve been contacted several times about adding the ability to enumerate ranges from the b+tree. It’s actually a very trivial thing to implement and I’ve handed out the code several times. With this release the following range enumeration methods will be available:

• EnumerateFrom(TKey start) – Enumerate from (inclusively) the specified key.
• EnumerateRange(TKey start, TKey end) – Enumerate from (inclusively) the start key until the next key follows the end key.

Example:

    var options = new BPlusTreeOptions<char, string>(PrimitiveSerializer.Char, PrimitiveSerializer.String);
    using(BPlusTree<char, string> btree = new BPlusTree<char,string>(options))
    {
        btree.AddRange(
            "qwertyuiopasdfghjklzxcvbnm"
            .ToCharArray()
            .Select(c => new KeyValuePair<char, string>(c, new String(c, 1)))
        );
        Assert.AreEqual(
            "jklmnop",
            new String(btree.EnumerateRange('j', 'p').Select(kv => kv.Key).ToArray())
        );
    }

Keys and Values Collections
The previous implementations of the properties Keys and Values have been re-implemented. They were doing a complete enumeration each time they where accessed. Now there is an actual class behind these that simply wraps the existing class-level enumeration. There is not, as yet, a means to enumerate only the keys or values from a range. Since there is not a performance benefit users should just use Linq’s .Select() extension to extract the key or value from the KeyValuePair as shown above.

First, Last, and TryGetFirst/Last
One project I was working with needed to be able to find the last key used in the dictionary so I could retrieve it’s value. Previously this meant you had to enumerate the entire dictionary. With ranged enumeration you might even been able to enumerate a small portion, but that is still a waste. The First() and Last() methods will now efficiently retrieve the key/value pairs for you. If there is a risk the dictionary is empty you can use the TryGetFirst() and TryGetLast() methods. These methods allow using the b+tree as a disk-based work queue of sorts (which is what I was doing, using a key-structure that sorts by priority, time, and then Guid).

Please note that the First() and Last() methods will throw InvalidOperationException if the collection is empty.

Let’s move on to bigger and better things…
Continue reading: Part 3 – AddRange and BulkInsert