1K 行 C 写了 3 年，这是我从业以来写过的最烧脑的代码！

[begeekmyfriend]

就这么一个数据结构玩意儿，B+树磁盘存储 CRUD： https://github.com/begeekmyfriend/bplustree

从 2014 年 9 月第一次提交了内存版本实现，到 2018 年 1 月的磁盘版本，总共（坚持）提交了近 200 次。。。

我已经没有力气去说明这三年都迭代了些什么，总之取得了这样的性能（视机器而定）

100W 插入——~3s
100W 删除——~3s
1KW 插入——<30s
1KW 删除——<30s
1 亿插入——<5min
1 亿删除——<5min
10 亿插入——~45min
10 亿删除——~45min

好吧，1 billion 那是我意淫的，我等不起这么多时间。。。读性能就不用列了吧，B+树你懂的

老实说 3 年前我就想写一个 DB，SQL 那种，但光一个 B+树耗了我 3 年最好的时光。我承认不是天才，3 年的迭代都是我犯过的浑与错误，一直坚持到现在。我以为与其写一个各方面都平庸的成品，不如写一个尽量做到极致的 demo，代码量基本维持在 1K 行。好歹也累积了 300+stars 了，感谢用户们的认可。

这种迭代是烧脑的，也是痛苦的。每一次对结构体的压榨，都要牵动数百行源文件的更改，有时候一个提交意味着一整个下午，我的大脑长时间处于马拉松选手泡在 20~30 公里处的感觉，相信不少同行都有过这种体验。。。

不多说了，大家认为有何改进的地方，欢迎交流~

测试机器是 ThinkPad T440 （不带字母）

有人把我的 B+树和其它语言版本的 B+树比。我要指出的是：
第一，你得把 CRUD 全部实现再说；
第二对于其它版本，只要实现 bug free 就 OK 了，而我用 C 花的大部分时间是要把性能做到极致。
最关键的一点，我没做出一个 database 出来，这是很大的遗憾，因为光是这么一个 demo 估计很多人用不上。不过我日常实在也没多少精力了，要不然也不会花 3 年。有心人可以自己单干，不用 PR 给我了（除了 bug 和优化）。

[shaco]

三年坚持一个 DEMO，值得尊敬！！

[skadi]

@begeekmyfriend 具体的没测,但是高效肯定能做到啊.

[soli]

@begeekmyfriend

回复 #26 楼：

不需要公平哈。
至少 Redis、MySQL 熟悉的人比较多，有个对比的话，比较容易在技术选型的时候做取舍。

[kylix]

楼主精神可嘉，顶一下！

[jyf]

如果是 kv 的话 可以考虑跟同领域的对比 也不一定非得是 sql 嘛 比如 sphia/wired tiger

[svenFeng]

本来不想说的，，，看到 append 的内容，你是可以试着实现一下并发的 B+tree，并且不再是一个独立的数据结构，而是作为整个带事务的数据库的一部分，就知道为什么不实现删除操作也是合理的了。

[begeekmyfriend]

@svenFeng 删除和插入本质都是一样的写操作而已，怎么并发就不能实现了？

[hugee]

大师

[svenFeng]

@begeekmyfriend 不是不能，而是考虑到性能和删除会引发一系列问题，代价太大完全不合算的，你可以看看 B-link tree，并发 B+树的一种变种，说不定就能理解这种权衡了

[jsfaint]

给楼主点赞！

[ahonn]

牛，虽然看不太懂。但是这个 1k 行代码能写 3 年就已经很了不起了。专研精神 Max

[frend94]

看了 lzGitHub，大佬哇

[begeekmyfriend]

@svenFeng 粗略浏览了一下 B-link，传说中的分布式索引？有文章证明了插入和查询线程之间的并发正确性，那是因为插入只会分裂新的节点，新分裂的节点不存在引用关系，故而可以避免竞态。而删除则会导致合并，对于已存在引用关系的节点，则必然导致竞态。故而只能用全局锁，对每一个 CRUD 操作加锁，就会损失性能，是这个意思吧？我很好奇如果没有删除，那么废弃的 key 怎么处理？

[begeekmyfriend]

@svenFeng 对于我目前实现的 B+树来说，实现插入 /查询的并发并非什么难事，我一共只用到 MIN_CACHE_NUM=5 个内存映射 node cache，对每一个 cache 加锁就可以了。

[fcten]

@begeekmyfriend 给 cache 加锁就是全局锁，插入、查询不应该使用全局锁

[begeekmyfriend]

@fcten 不是吧，一个 cache 对应一个 node 啊，只是在操作内部引用 cache 的时候才上锁。全局锁指的是整个 tree 用一把锁，这才是对 CRUD 操作上锁。

[begeekmyfriend]

@fcten 不同 cache 对应的 node 如果不存在引用关系，那么就不存在竞态问题和互斥处理

[fcten]

@begeekmyfriend 你不是说只有 5 个 cache 吗，那就是对应 5 个锁了？我不清楚你的具体实现，你这样能做到 5 个以上的并发吗？

[fcten]

@begeekmyfriend 而且，你的 node 对应了很多记录吧。理论上最优的话应该是操作某个记录就只给这个记录加锁。对整个 block 加锁会锁住很多无关的记录

[begeekmyfriend]

@fcten
1、cache 数目跟线程数目有关系吗？ 1W 个线程引用 cache A，只会用一把锁互斥啊
2、cache A 的锁又不会给 cache B 上锁，这在分裂新节点情况下是不存在竞态的。

[begeekmyfriend]

@fcten 没听说过一条记录一把锁的，底层只关注 node，你是不是没搞清楚概念？

[fcten]

@begeekmyfriend
1、一万个线程竞争一把锁，这是一个并发，而不是一万个并发
2、可以搜索一下 mysql 的行级锁

[begeekmyfriend]

@fcten 行级锁那是上层概念，底层怎么可能每一条记录上锁？

[fcten]

@begeekmyfriend 不知道你的上层概念指的是什么，但是 mysql 行级锁是通过给索引的每一项上锁来实现的。

[begeekmyfriend]

@fcten 就是上层的缓存啊，底层（包括我的 cache ）指的是落地用的

[fcten]

@begeekmyfriend 你给整个 cache 加锁了，那上层调用你的时候不一样被锁住了吗。上层做细粒度的锁还有什么意义……

[svenFeng]

@begeekmyfriend 从数据库的角度考虑的话，只需要从索引中找出记录所属于的块，删掉就可以了，索引的 key 不需要处理，B+树有多余的 key 并不是什么问题，反正你顺着 key 往下找，发现记录不在了，那就是删掉了。考虑到实际的应用场景，其实数据库用到 delete 的操作非常非常少，大家在项目中都是维护一个 deleted 字段，删除就是把这个字段置为 1 就可以了。在极少数需要物理删除的情况，索引不删除 key，记录块不删除确实会造成膨胀的问题，发现有效记录过少的情况，直接重建就可以了。

[huanghaofu86]

群主，想进入 BI 大数据行列，这路子，怎么走，有 3 年数据库开发经验

[huanghaofu86]

@begeekmyfriend 楼主，是否可以交个朋友？

[begeekmyfriend]

@huanghaofu86 我没有 DB 开发经验，全是业余作品

[zhicheng]

实现一个不支持 variable size key 不支持 mvcc 不支持 acid 的单线程 B+tree 并不是什么难事（包括半分钟内写入 10M keys ），写了 3 年我不作评价。

在工程实践中，DELETE 命令删除的数据一般不是立即从 B+tree 中删除，大多是 mark delete，一是为了实现 MVCC，二是高并发涉及 merge 和 shift 的 delete 算法比较复杂。真正的删除往往是在 VACUUM 的时候批量删除。

并发 B+tree 有好几种方法，高性能的并发 B+tree 并不是像你想的那么简单，具体可以看相关论文了。