This is a general-purpose key-value database format that uses an SBSF container as its backing store.


This header is found at the start of the User Header area of the SBSF container.

Byte[4]Signature "BTDB"
Uint64Root Block ID
BoolIs Root Leaf
PackedMetadata length
StringDatabase Signature
Uint32Key Size

Root Block ID
Block ID where the Root Node can be found.
Is Root Leaf
Specifies the format of the Root Node. If this is set, then the Root is stored in Leaf Format, otherwise it is stored in Index Format.
Database Signature
Identifies which format used this database as a container. The pages that describe those formats will document which Signature should be here.
Key Size
Specifies the size in bytes for all keys used in this database. The pages that describe formats which use this container will specify which Key Size is used.

Leaf Block Format

Since this database uses the SBSF format as its backing store, all data is stored in blocks. The problem is that a single Leaf can be larger than a single block. To compensate for this, leaves are cut up and stored in this Leaf Block Format.

Byte[2]Leaf Block Signature "LL"
Byte[*]Leaf Data
Int64Next Leaf Block ID

Let's assume the Block Size is set to 512 bytes. Each block contains 2 bytes of signature, 502 bytes of Leaf data, and 8 bytes that point to the next block. If the Next Leaf Block ID is -1, then there aren't any more Leaf Blocks.

Leaf Format

Now let's look at the format of the actual leaf inside the Leaf Blocks.

Uint32Number of Children
PackedValue Length

The children are sorted by their keys. This allows you to use binary searching to search for the matching key in Log time.

Index Format

The Indexes are also stored in blocks, but they're always smaller than a single block, so they don't need to be cut up into multiple Index Blocks.

Byte[2]Index Block Signature "II"
Uint32Number of Children
Uint64Default Block ID
Byte[*]Minimum Key
Uint64Block ID

Again, the children are sorted by their keys to allow for binary searching.

This specifies the depth of the tree. When this is 0, the Block IDs of the children point to Leaf Nodes, otherwise they point to other Index Nodes.
Minimum Key
This specifies the minimum key value that might be found in the corresponding Block ID. While searching, you'll want to find the highest Minimum Key that is less than or equal to your key.
Default Block ID
This is the Block ID to use for any keys that less than the lowest Minimum Key.

Searching Algorithm

Here's some pseudocode that demonstrates how to search through the btree for a key. This pseudocode uses linear searching instead of binary searching for clarity.

find(Key key)
	if (rootIsLeaf)
		return findLeaf(rootBlockID,key);
		return findIndex(rootBlockID,key);

findLeaf(Uint64 blockID,Key key)
	Leaf leaf = loadLeaf(blockID);
	foreach (child in leaf)
		if (child.key == key)
			return child.value;
	return null;

findIndex(Uint64 blockID,Key key)
	Index index = loadIndex(blockID);
	Uint64 valueID = index.defaultBlockID;
	foreach (child in index)
		if (child.minimumKey > key)
		valueID = child.blockID;
	if (index.level == 0)
		return findLeaf(valueID,key);
		return findIndex(valueID,key);