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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

For Existing Member Sign In

• 请不要在回答技术问题时复制粘贴 AI 生成的内容

This topic created in 3016 days ago, the information mentioned may be changed or developed.

就这么一个数据结构玩意儿，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 公里处的感觉，相信不少同行都有过这种体验。。。

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

Supplement 1 · Jan 23, 2018

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

Supplement 2 · Jan 24, 2018

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

min

插入

删除

提交

131 replies • 2018-01-24 16:27:34 +08:00

1 2

❮

❯

wangmm

Jan 23, 2018

厉害程序小白摩拜！

hahasong

Jan 23, 2018 via iPhone

程序小白 OFO

Applenice

Jan 23, 2018

程序小白小蓝

allen6699

Jan 23, 2018

程序小白滴滴

xjr1022

Jan 23, 2018

程序小白滴滴

Ethous

Jan 23, 2018 via Android

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

stoldog

Jan 23, 2018

程序小白 HelloBike

zorui

Jan 23, 2018

程序小白小鸣

xntop

Jan 23, 2018

关键是视机器而定，哈哈

jzds001

Jan 23, 2018

赞坐

owenliang

Jan 23, 2018

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

ZyZyZzz

Jan 23, 2018 via Android

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

ynyounuo

Jan 23, 2018

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

jadec0der

Jan 23, 2018

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

Applenice

Jan 23, 2018

去点了 star~~~

wowo243

Jan 23, 2018 via Android

我是来看回复的。。。

luckychenhaha

Jan 23, 2018

666，先 star 为敬

jecshcier

Jan 23, 2018 via iPhone

看回复来的。。。

codexu

Jan 23, 2018

给大佬递 star

soli

Jan 23, 2018

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

lazypu

Jan 23, 2018

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

kaiser1992

Jan 23, 2018

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

supercaizehua

Jan 23, 2018 via Android

程序小白哈罗

scriptB0y

Jan 23, 2018

程序小白捷达

begeekmyfriend

Jan 23, 2018

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

begeekmyfriend

Jan 23, 2018

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

loading

Jan 23, 2018

滴幼儿票

zxybird

Jan 23, 2018

点个 star，予以支持

dobug

Jan 23, 2018

YouXia

Jan 23, 2018

赞！

Andiry

Jan 23, 2018

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

begeekmyfriend

Jan 23, 2018

@Andiry 还没做到这一步

cnwtex

Jan 23, 2018

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

Andiry

Jan 23, 2018

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

begeekmyfriend

Jan 23, 2018

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

begeekmyfriend

Jan 23, 2018

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

cnwtex

Jan 23, 2018

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

begeekmyfriend

Jan 23, 2018

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

anubiskong

Jan 23, 2018

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

JanKinAn

Jan 23, 2018 via Android

我默默的删掉了我的 gayhub 库

duesicilie

Jan 23, 2018

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

exch4nge

Jan 23, 2018

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

begeekmyfriend

Jan 23, 2018

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

zpf124

Jan 23, 2018

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

zouqiang

Jan 23, 2018

膜拜

fcten

Jan 23, 2018

file: bplustree.c
line: 1079

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

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

begeekmyfriend

Jan 23, 2018

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

fcten

Jan 23, 2018

@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

Jan 23, 2018

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

chenweidong

Jan 23, 2018

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

begeekmyfriend

Jan 23, 2018

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

daozhihun

Jan 23, 2018 via Android

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

begeekmyfriend

Jan 23, 2018

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

acros

Jan 23, 2018

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

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

hsuan

Jan 23, 2018 via Android

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

stabc

Jan 23, 2018

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

closedevice

Jan 23, 2018

不错，加油

0915240

Jan 23, 2018

给大佬端茶倒水

jeffciu

Jan 23, 2018 via iPhone

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

likuku

Jan 23, 2018

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

feng32

Jan 23, 2018 via Android

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

begeekmyfriend

Jan 23, 2018

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

begeekmyfriend

Jan 23, 2018

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

unique

Jan 23, 2018 via iPhone

为楼主的坚持点赞👍🏾

rashawn

Jan 23, 2018 via iPhone

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

rashawn

Jan 23, 2018 via iPhone

https://github.com/NicolasLM/bplustree

rashawn

Jan 23, 2018 via iPhone

感觉你们两个是有缘人

begeekmyfriend

Jan 23, 2018

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

begeekmyfriend

Jan 23, 2018

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

letianqiu

Jan 23, 2018

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

begeekmyfriend

Jan 23, 2018

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

HaoyangWei

Jan 23, 2018

滋瓷~
佩服楼主的毅力

szhaoliang

Jan 23, 2018 via Android

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

waterlaw

Jan 23, 2018

楼主 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':

```