How to Build a Persistent B+ Tree for Range Queries
A dictionary answers "give me the value for this key", although many applications also need "give me every entry between these two keys, in order". Answering that from a file normally means scanning and sorting, or maintaining an ordered index by hand. StreamMappedBTreePlus<K, V> in Sphere10 Framework is an ordered dictionary that keeps its nodes in a stream, so the index persists and a range query reads only the part of the tree it needs.
This article creates a B+ tree over a file, fills it, reopens it and runs an inclusive range query. It also explains the stored layout, the fixed-size key and value requirement, and the settings that must be repeated on reopen.
1. A first look
The constructor takes the tree order, the backing stream and one serializer each for keys and values.
using (var file = File.Open(treePath, FileMode.Create, FileAccess.ReadWrite)) {
using var tree = new StreamMappedBTreePlus<long, int>(order, file, PrimitiveSerializer<long>.Instance, PrimitiveSerializer<int>.Instance);
foreach (var key in Enumerable.Range(0, count).Reverse())
tree.Add(key, key % 7);
}
The sample inserts 20,160 long keys in descending order, and the tree keeps them sorted as they arrive. Opening an existing tree uses the same constructor over the existing stream, with the original order and serializers.
using var reopenedFile = File.Open(treePath, FileMode.Open, FileAccess.ReadWrite);
using var reopened = new StreamMappedBTreePlus<long, int>(order, reopenedFile, PrimitiveSerializer<long>.Instance, PrimitiveSerializer<int>.Instance);
var range = reopened.FindRange(from, through).ToArray();
With from at 10,080 and through at 10,139, FindRange returns sixty entries in ascending key order, read from the file the first block wrote.
2. How the tree is stored
In a B+ tree, internal nodes hold only separator keys that direct a search, and every key/value entry lives in a leaf. Each leaf also links to the next leaf, which makes the leaves an ordered chain.
FindRange(lower, upper) descends from the root to the leaf that would contain the lower bound, then follows the leaf links and yields entries until a key exceeds the upper bound. Both bounds are inclusive and the results arrive in key order. In the tree above, FindRange(20, 60) starts in the first leaf and ends in the third without returning to the internal node.
StreamMappedBTreePlus<K, V> writes this structure directly to a seekable stream. The stream starts with a 32-byte header that records the root node, the entry count and the number of recycled nodes. Fixed-size node records follow it. Every node has the same size, which is derived from the tree order and the serialized sizes of the key and the value, so a node's position is a simple multiplication and no allocation table is needed.
The first two rows are the header, and the remaining rows are one node record, drawn without regard to scale. A leaf fills its entry slots with keys and values and records the handle of the next leaf. An internal node uses only the key part of each entry slot, together with the child handles.
3. Create and fill the tree
The tree in the first look was filled through Add, which is a dictionary member. The class implements IBTree<K, V>, which is an IDictionary<K, V> with a few ordered operations added.
| Member | Purpose |
Add, Remove, TryGetValue, indexer |
The standard dictionary operations. |
Set(key, value, overwriteIfExists) |
Inserts an entry, or replaces an existing value when asked to. |
FindRange(lowerInclusive, upperInclusive) |
Enumerates an inclusive key range in comparer order. |
Order, Comparer |
The node fan-out and the key ordering in use. |
Validate(out error) |
Checks the tree invariants and reports the first failure. |
The constructor arguments define the file layout.
| Argument | Notes |
order |
The maximum number of children per node, with a minimum of 3. A constructor overload without it uses the Framework default of 2048, and that overload accepts only an empty stream. |
keySerializer, valueSerializer |
Both must be constant-size, because nodes are fixed-size records. The constructor rejects a variable-size serializer. |
keyComparer |
Optional key ordering. It defaults to Comparer<K>.Default. |
endianness |
Byte order of the stored data. |
4. Reopen and query a range
FindRange is a lazy enumerable of key/value pairs, so the query reads nodes as the caller consumes results. The first look consumed the whole range at once with ToArray.
The file does not record its order or its serializers. On open, the constructor checks that the stream length and root record are consistent with the supplied layout and throws InvalidDataFormatException when they are not. That check catches many mismatches but cannot prove the settings are the original ones, so keep them with the code or configuration that owns the file.
5. Limits and related types
-
Fixed-size keys and values. Store a variable-size payload elsewhere, for example in a
stream-mapped list
, and keep its position or identifier as the tree value.
-
Unique keys. The tree is a dictionary. For several values per key, use
StreamMappedBTreeLookup<K, V>, which stores a one-to-many lookup over the same kind of tree. -
No transaction. Each change is written to the stream as it happens, and disposing the tree flushes the final header. Place the stream behind a transactional owner when a batch of inserts must be applied together.
-
Caller-owned stream. Disposing the tree does not close the stream, so dispose the tree first and the stream after it.
StreamMappedBTree<K, V> is the plain B-tree counterpart, which keeps entries in internal nodes as well. StreamMappedFactory.CreateBTreePlus, CreateBTree and CreateBTreeLookup construct the same types when a factory call reads better.
6. Get the package and run the sample
Add the package to a .NET 10 project.
dotnet add package Sphere10.Framework
StreamMappedBTreePlus<K, V> ships in the Sphere10.Framework NuGet package. Download the sample project. It fills the tree, reopens it and checks that the range query returns exactly the expected keys in order. Use the .NET 10 SDK and Sphere10 Framework.
dotnet run -c Release -- ./fresh-example-dataEntries after reopen: 20160
Range 10080 through 10139: 60 entries in key order
First: 10080=0; last: 10139=3Download the complete NuGet sample project. The archive contains the project, its model files and run instructions. Keep the pinned package version when reproducing the example.
The Sphere10 Framework overview describes the rest of the toolkit.
Author: Herman Schoenfeld
