Python3在磁盘上的B＋树：Bplustree

Bplustree

Python3在磁盘上的B+树。

它就像一个字典，但存储在磁盘上。那么什么时候使用它呢？

要存储的数据不适合存在内存里时

数据需要被持久化时

键的顺序很重要时

此项目正在开发中，不同版本的文件格式会有所不同；因此，该数据不要用作您主要的数据来源。

快速开始

用pip安装Bplustree：

创建存储在文件中的B+树索引，并按如下方式使用它：

键和值

键必须具有自然顺序，并且必须可序列化成字节；其中提供了最常见类型的一些默认序列化程序，例如，索引UUID：

另一方面，值总是字节。它们可以是任意长度的，参数value_size=128定义了在树本身中可以存储的值的大小上限。超出此限制的值将存储在溢出页面中，每个溢出值至少占满一页。

迭代

由于键有顺序，所以按顺序检索元素是非常有效的：

也可以通过给出Python片段遍历树的子集：

两种方法都使用一个生成器，所以它们不需要将整个内容加载到内存中，而是将树的一部分复制到字典中也是可以的：

并发性

树是线程安全的，它支持多用户读取/单用户写入。

如下是安全的：

在多个线程之间共享一个BPlusTree实例。

如下是不安全的：

在多个进程之间的共享一个BPlusTree实例。

创建指向同一文件的多个BPlusTree实例。

持久化

预写日志（WAL）用于确保数据安全。对树所做的所有更改都附加到WAL中，通常在关闭树时，仅在检查点的操作中才会合并到树中。这种方法来自于其他数据库的启发，例如SQLite。

如果树没有正确关闭（停电，进程停止...），WAL文件会在下一次树被打开时合并。

性能

像任何数据库一样，有许多方法可以微调引擎并获得最佳性能：

order或分支因子，定义每个节点将容纳多少条目；

page_size是分配给一个节点的字节数量和读写操作的长度，最好保持接近磁盘的块大小；

cache_size保持频繁使用的节点，大缓存防止了从原始页面创建Python对象的昂贵操作，但是使用了更多的内存。

有效使用树的一些建议：

如果可能的话，按照升序插入元素，首选UUID v1到UUID v4；

使用tree.batch_insert(iterator)批量插入，而不是循环使用tree.insert()；

迭代使用树，而不是在循环中使用tree.get()；

如果插入很多使用tree.checkpoint()，这将防止WAL无限增长；

使用小键和值，相应地设置其限制和溢出值；

将文件和WAL存储在快速磁盘上；

许可证

MIT

英文原文：https://github.com/NicolasLM/bplustree

译者：掌心化雪