Repository files navigation

An on-disk B+tree for Python 3.

It feels like a dict, but stored on disk. When to use it?

• When the data to store does not fit in memory
• When the data needs to be persisted
• When keeping the keys in order is important

This project is under development: the format of the file may change betweenversions. Do not use as your primary source of data.

Install Bplustree with pip:

pip install bplustree

Create a B+tree index stored on a file and use it with:

>>>frombplustreeimportBPlusTree>>>tree=BPlusTree('/tmp/bplustree.db',order=50)>>>tree[1]=b'foo'>>>tree[2]=b'bar'>>>tree[1]b'foo'>>>tree.get(3)>>>tree.close()

Keys must have a natural order and must be serializable to bytes. Some defaultserializers for the most common types are provided. For example to index UUIDs:

>>>importuuid>>>frombplustreeimportBPlusTree,UUIDSerializer>>>tree=BPlusTree('/tmp/bplustree.db',serializer=UUIDSerializer(),key_size=16)>>>tree.insert(uuid.uuid1(),b'foo')>>>list(tree.keys())[UUID('48f2553c-de23-4d20-95bf-6972a89f3bc0')]

Values on the other hand are always bytes. They can be of arbitrary length,the parametervalue_size=128 defines the upper bound of value sizes thatcan be stored in the tree itself. Values exceeding this limit are stored inoverflow pages. Each overflowing value occupies at least a full page.

Since keys are kept in order, it is very efficient to retrieve elements inorder:

>>>foriintree:...print(i)...12>>>forkey,valueintree.items():...print(key,value)...1b'foo'2b'bar'

It is also possible to iterate over a subset of the tree by giving a Pythonslice:

>>>forkey,valueintree.items(slice(start=0,stop=10)):...print(key,value)...1b'foo'2b'bar'

Both methods use a generator so they don't require loading the whole contentin memory, but copying a slice of the tree into a dict is also possible:

>>>tree[0:10]{1:b'foo',2:b'bar'}

The tree is thread-safe, it follows the multiple readers/single writer pattern.

It is safe to:

• Share an instance of aBPlusTree between multiple threads

It is NOT safe to:

• Share an instance of aBPlusTree between multiple processes
• Create multiple instances ofBPlusTree pointing to the same file

A write-ahead log (WAL) is used to ensure that the data is safe. All changesmade to the tree are appended to the WAL and only merged into the tree in anoperation called a checkpoint, usually when the tree is closed. This approachis heavily inspired by other databases like SQLite.

If tree doesn't get closed properly (power outage, process killed...) the WALfile is merged the next time the tree is opened.

Like any database, there are many knobs to finely tune the engine and get thebest performance out of it:

• order, or branching factor, defines how many entries each node will hold
• page_size is the amount of bytes allocated to a node and the length ofread and write operations. It is best to keep it close to the block size ofthe disk
• cache_size to keep frequently used nodes at hand. Big caches prevent theexpensive operation of creating Python objects from raw pages but use morememory

Some advices to efficiently use the tree:

• Insert elements in ascending order if possible, prefer UUID v1 to UUID v4
• Insert in batch withtree.batch_insert(iterator) instead of usingtree.insert() in a loop
• Let the tree iterate for you instead of usingtree.get() in a loop
• Usetree.checkpoint() from time to time if you insert a lot, this willprevent the WAL from growing unbounded
• Use small keys and values, set their limit and overflow values accordingly
• Store the file and WAL on a fast disk

MIT