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

Header

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

Byte[4]	Signature "BTDB"
Uint64	Root Block ID
Bool	Is Root Leaf
Byte[19]	Reserved
Packed	Metadata length
Metadata	String Database Signature Uint32 Key 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
Int64	Next 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.

Uint32	Number of Children
Child[*]	Byte[*] Key Packed Value Length Byte[*] Value

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"
Byte	Level
Uint32	Number of Children
Uint64	Default Block ID
Child[*]	Byte[*] Minimum Key Uint64 Block ID

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

Level

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);
	else
		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)
			break;
		valueID = child.blockID;
	}
	if (index.level == 0)
		return findLeaf(valueID,key);
	else
		return findIndex(valueID,key);
}