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 和优化）。

[wangmm]

厉害 程序小白摩拜！

[hahasong]

程序小白 OFO

[Applenice]

程序小白 小蓝

[allen6699]

程序小白 滴滴

[xjr1022]

程序小白 滴滴

[Ethous]

一件事，能坚持做三年。这种毅力值得点赞！

[stoldog]

程序小白 HelloBike

[zorui]

程序小白 小鸣

[xntop]

关键是视机器而定，哈哈

[jzds001]

赞坐

[owenliang]

红黑书与 B 树是我从来没试图写过的数据结构，虽然后面 K/V 时代出现了更多牛逼的树，但都很难！

[ZyZyZzz]

@Livid 这是一个极好的主题贴，然而你来看看我楼上都回复了些什么

[ynyounuo]

恭喜你，你的心里有了 B 树

[jadec0der]

lz 牛逼啊，这么有耐心，佩服佩服

[Applenice]

去点了 star~~~

[wowo243]

我是来看回复的。。。

[luckychenhaha]

666，先 star 为敬

[jecshcier]

看回复来的。。。

[codexu]

给大佬递 star

[soli]

不来个横向对比么？
比如和 Redis、MySQL 等对比一下性能？

[linxl]

不知道你在说什么, 但是我也会摩拜

[kaiser1992]

有必要把 benchmark 测试结果贴出来

[supercaizehua]

程序小白 哈罗

[scriptB0y]

程序小白 捷达

[begeekmyfriend]

@kaiser1992 IO 的东西跟机器相关，做不到很公正吧

[begeekmyfriend]

@soli Redis 和 MySQL 两者之间对比都是不公正的

[loading]

滴 幼儿票

[zxybird]

点个 star，予以支持

[dobug]

点赞

[YouXia]

赞！

[Andiry]

初看了一下有问题啊，node_flush()里只有 pwrite 没有 fsync，如何能保证数据落到磁盘呢？支持 failure recovery 吗？

[begeekmyfriend]

@Andiry 还没做到这一步

[cnwtex]

没有一个 issue, 这种东西有人在用吗?

[Andiry]

@begeekmyfriend 那样的话这个性能测试没啥意义了，因为本质还是内存版本。

[begeekmyfriend]

@Andiry 因为我还没想好怎么加，最笨的方法，你直接在 write 后面 sync 再测一下呗，慢不了的

[begeekmyfriend]

@cnwtex 我关闭了，另外，老外都 email 了

[cnwtex]

@begeekmyfriend 不好意思, 没做过开源项目. 都 email 的话, 是你的客户吧?
我搂了一眼, 暂时用不上, 加油!

[begeekmyfriend]

@cnwtex 据我所知，star 的好多都是前端的，估计不想用数据库。。。

[anubiskong]

现在时代这么浮躁，难得有你这么坚持做一件事的人，加油

[JanKinAn]

我默默的删掉了我的 gayhub 库

[duesicilie]

滴！发生了什么？这不是个上班时间灌水用的地儿吗

[exch4nge]

在精神上支持 LZ。不过不知道什么场景下会用 LZ 这种库，生产环境下 leveldb 是更好的一种选择吧。

[begeekmyfriend]

@exch4nge 本来是想写个 database 的，但按照进度估计写不动了，做到这地步，交接给有缘人吧

[zpf124]

只能称赞一句，但我技术差太多而且没有什么毅力估计没法模仿大佬的历程。

[zouqiang]

膜拜

[fcten]

file: bplustree.c
line: 1079

_max_order = (block_size - sizeof(node)) / (sizeof(key_t) + sizeof(off_t));

有符号数与无符号数一起运算，导致 block_size < sizeof(node) 时返回非预期的结果

[begeekmyfriend]

@fcten 你给 block_size 设置了一个多大的数？

[fcten]

@begeekmyfriend
-- B+tree setting...
Set data index file name (e.g. /tmp/data.index):
Set index file block size (bytes, power of 2, e.g. 4096): 4
config node order:1431655762 and leaf entries:1431655762
Please input command (Type 'h' for help): i 1
Segmentation fault (core dumped)

[skadi]

如果只是数据结构的话,大学的时候 b 树以及几个变种自己都手动实现过.并不觉得...

[chenweidong]

吊就一个字，我只说一次。

[begeekmyfriend]

@fcten fixed https://github.com/begeekmyfriend/bplustree/commit/42e8303d55043eb3c2f998c35cb4be6a93ff36c3

[daozhihun]

歪个楼，楼主的头像我第一眼看以为是刑舅舅 😂

[begeekmyfriend]

@skadi 半分钟内插入 1KW 个 key 再说，不然就是假的 B 树

[acros]

捂着脸说一句：我看不懂（其实也压根没看，B+树磁盘存储 CRUD 几个关键字好像离我很远）。

能搭配开发博客看就好了，或者随便写写开发心得啊。
比如 rapidjson 的这个做法，博客比代码容易引流嘛：
https://github.com/Tencent/rapidjson
https://zhuanlan.zhihu.com/p/20029820

[hsuan]

挺好的，不过想不到有啥用

[stabc]

既然说了“视机器而定”，为什么不把你的性能测试的机器硬件贴出来呢？

[closedevice]

不错，加油

[0915240]

给大佬端茶倒水

[jeffciu]

没仔细研究过 B+树，但还是佩服楼主的成果

[likuku]

1K 行能写这种底层硬功能，也真是了不起!

[feng32]

赞一个
因为业务关系，我现在只记得 k-d 树的写法了

[begeekmyfriend]

@feng32 KD 树我也有，要不要 PK 一下： https://github.com/begeekmyfriend/kdtree

[begeekmyfriend]

@stabc 懒得贴了，thinkpad t440，后面没字母

[unique]

为楼主的坚持点赞👍🏾

[rashawn]

为啥 trending 上有个一样名字的项目 但不是楼主写的 好奇怪

[rashawn]

https://github.com/NicolasLM/bplustree

[rashawn]

感觉你们两个是有缘人

[begeekmyfriend]

@rashawn 你看他 issue，没实现删除，骗 star 来着～

[begeekmyfriend]

@acros 人家那是正式发布到很多版本后才写博客的，我连个 database 都没力气写了

[letianqiu]

正好在看 B 树，有个问题没有懂，想请教。B 树究竟如何减少磁盘 I/O ？如果 B 树节点里有记录储存在硬盘里的实际地址，那么这个地址是怎么得到的？在写文件之前应该是拿不到实际地址的？如果写完才能拿到，那么是不是再将地址写入？

[begeekmyfriend]

@letianqiu 我写的是 B+树。
如果要减少磁盘 I/O 那么尽量一个节点容纳多个索引，索引节点越少，读操作 I/O 次数越少，查询越快，但也不能太多，否则插入删除就需要相关子节点全部更新，这就是为什么 B 树的写效率偏低。
我是基于 POSIX 实现的，不是裸机，所以存储的是文件，实际地址自然是文件字节偏移，后面该如何处理你应该明白

[HaoyangWei]

滋瓷~
佩服楼主的毅力

[szhaoliang]

都坚持三年了再坚持一下，当初我就是打算做一下别的放松放松再回来，结果现在就只能给大佬倒茶水了......

[waterlaw]

楼主 Linux 下报如下错误：
```
/home/zjp/Projects/bplustree/tests/bplustree_demo.c: In function ‘ bplus_tree_setting ’:
/home/zjp/Projects/bplustree/tests/bplustree_demo.c:29:25: error: this statement may fall through [-Werror=implicit-fallthrough=]
printf("\n");
^~~~~~~~~~~~
/home/zjp/Projects/bplustree/tests/bplustree_demo.c:30:17: note: here
case 'q':
^~~~
/home/zjp/Projects/bplustree/tests/bplustree_demo.c:54:25: error: this statement may fall through [-Werror=implicit-fallthrough=]
printf("\n");
^~~~~~~~~~~~
/home/zjp/Projects/bplustree/tests/bplustree_demo.c:55:17: note: here
case 'q':

```

[wujunze]

大神 厉害了 观摩一下代码

[begeekmyfriend]

@waterlaw 你这是 clang 吧，还是 demo 测试里的，我没有在 switch-case 里用 break，有意为之，编译选项过于严格了。

[Rorysky]

有毅力，观摩学习下代码~

[crayhuang]

膜拜～

[bigeast]

巧了，今天在 hacker news 上看到一条推送，也是一个 B+树，名字都一模一样，https://github.com/NicolasLM/bplustree

不过是用 python 写的。

[begeekmyfriend]

@bigeast 那个还没有删除操作

[deali]

默默点赞

[caola]

程序小白 优拜

[Dxer]

只能默默地为你点赞

[Michaelssss]

默默点赞

[jadeity]

@ZyZyZzz 现在再看看楼下

[TreStone]

楼主代码风格真是漂亮，打算将楼主 B+树移植到嵌入式平台，目前有一处不是很明白，“ struct free_block ”作用是什么？烦请楼主解惑。

[silianbo]

mark

[begeekmyfriend]

@TreStone 那是删除后留下的空节点，可供后来者插入

[lxrmido]

学习一下，膜拜

[shiyouming91]

楼主厉害 这个可能也有参考价值 http://www.lmdb.tech/doc/index.html

[wsb200514]

膜拜

[iamnoten]

厉害

[bojackhorseman]

@daozhihun #52 团座大人

[bojackhorseman]

@daozhihun #52 啊，错了，是师座。

[nuanyang]

膜拜

[hasbug]

程序小白 嘟嘟

[cstj0505]

佩服 lz 的坚持

[zchzch1014]

楼主做的事就像自己的名字一样，敬佩

[hellboys]

我感觉楼主更牛逼的是这个哈
https://github.com/begeekmyfriend/leetcode