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

V2EX = way to explore

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

现在注册

已注册用户请登录

这是一个创建于 2483 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

第 1 条附言 · 2018-01-23 19:43:47 +08:00

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

第 2 条附言 · 2018-01-24 00:29:36 +08:00

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

min

插入

删除

提交

131 条回复 • 2018-01-24 16:27:34 +08:00

1 2

❮

❯

wangmm

2018-01-23 15:13:21 +08:00

厉害程序小白摩拜！

hahasong

2018-01-23 15:14:49 +08:00 via iPhone

程序小白 OFO

Applenice

2018-01-23 15:17:52 +08:00

程序小白小蓝

allen6699

2018-01-23 15:19:43 +08:00

程序小白滴滴

xjr1022

2018-01-23 15:20:37 +08:00

程序小白滴滴

Ethous

2018-01-23 15:22:29 +08:00 via Android

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

stoldog

2018-01-23 15:23:27 +08:00

程序小白 HelloBike

zorui

2018-01-23 15:26:00 +08:00

程序小白小鸣

xntop

2018-01-23 15:36:14 +08:00

关键是视机器而定，哈哈

jzds001

2018-01-23 15:37:27 +08:00

赞坐

owenliang

2018-01-23 15:46:18 +08:00

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

ZyZyZzz

2018-01-23 15:46:37 +08:00 via Android

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

ynyounuo

2018-01-23 15:52:20 +08:00

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

jadec0der

2018-01-23 15:52:41 +08:00

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

Applenice

2018-01-23 15:55:12 +08:00

去点了 star~~~

wowo243

2018-01-23 15:56:39 +08:00 via Android

我是来看回复的。。。

luckychenhaha

2018-01-23 16:01:23 +08:00

666，先 star 为敬

jecshcier

2018-01-23 16:08:20 +08:00 via iPhone

看回复来的。。。

codexu

2018-01-23 16:12:36 +08:00

给大佬递 star

soli

2018-01-23 16:13:11 +08:00

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

linxl

2018-01-23 16:13:32 +08:00

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

kaiser1992

2018-01-23 16:15:30 +08:00

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

supercaizehua

2018-01-23 16:16:59 +08:00 via Android

程序小白哈罗

scriptB0y

2018-01-23 16:24:25 +08:00

程序小白捷达

begeekmyfriend

2018-01-23 16:28:06 +08:00

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

begeekmyfriend

2018-01-23 16:29:14 +08:00

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

loading

2018-01-23 16:30:59 +08:00

滴幼儿票

zxybird

2018-01-23 16:36:20 +08:00

点个 star，予以支持

dobug

2018-01-23 16:43:08 +08:00

YouXia

2018-01-23 16:46:06 +08:00

赞！

Andiry

2018-01-23 16:47:24 +08:00

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

begeekmyfriend

2018-01-23 16:51:53 +08:00

@Andiry 还没做到这一步

cnwtex

2018-01-23 16:54:51 +08:00

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

Andiry

2018-01-23 16:55:28 +08:00

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

begeekmyfriend

2018-01-23 16:57:01 +08:00

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

begeekmyfriend

2018-01-23 16:58:26 +08:00

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

cnwtex

2018-01-23 17:02:15 +08:00

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

begeekmyfriend

2018-01-23 17:05:03 +08:00

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

anubiskong

2018-01-23 17:06:09 +08:00

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

JanKinAn

2018-01-23 17:10:50 +08:00 via Android

我默默的删掉了我的 gayhub 库

duesicilie

2018-01-23 17:36:25 +08:00

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

exch4nge

2018-01-23 17:44:37 +08:00

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

begeekmyfriend

2018-01-23 17:48:21 +08:00

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

zpf124

2018-01-23 17:50:35 +08:00

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

zouqiang

2018-01-23 17:55:24 +08:00

膜拜

fcten

2018-01-23 18:01:37 +08:00

file: bplustree.c
line: 1079

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

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

begeekmyfriend

2018-01-23 18:03:38 +08:00

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

fcten

2018-01-23 18:06:37 +08:00

@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

2018-01-23 18:20:52 +08:00

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

chenweidong

2018-01-23 18:24:21 +08:00

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

begeekmyfriend

2018-01-23 18:27:55 +08:00

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

daozhihun

2018-01-23 18:29:50 +08:00 via Android

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

begeekmyfriend

2018-01-23 18:35:00 +08:00

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

acros

2018-01-23 18:45:45 +08:00

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

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

hsuan

2018-01-23 19:08:34 +08:00 via Android

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

stabc

2018-01-23 19:11:11 +08:00

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

closedevice

2018-01-23 19:16:33 +08:00

不错，加油

0915240

2018-01-23 19:20:19 +08:00

给大佬端茶倒水

jeffciu

2018-01-23 19:22:43 +08:00 via iPhone

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

likuku

2018-01-23 19:24:10 +08:00

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

feng32

2018-01-23 19:31:48 +08:00 via Android

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

begeekmyfriend

2018-01-23 19:32:39 +08:00

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

begeekmyfriend

2018-01-23 19:34:30 +08:00

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

unique

2018-01-23 19:37:09 +08:00 via iPhone

为楼主的坚持点赞👍🏾

rashawn

2018-01-23 20:37:48 +08:00 via iPhone

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

rashawn

2018-01-23 20:39:04 +08:00 via iPhone

https://github.com/NicolasLM/bplustree

rashawn

2018-01-23 20:41:01 +08:00 via iPhone

感觉你们两个是有缘人

begeekmyfriend

2018-01-23 21:26:41 +08:00

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

begeekmyfriend

2018-01-23 21:33:59 +08:00

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

letianqiu

2018-01-23 21:56:03 +08:00

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

begeekmyfriend

2018-01-23 22:07:03 +08:00

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

HaoyangWei

2018-01-23 22:19:28 +08:00

滋瓷~
佩服楼主的毅力

szhaoliang

2018-01-23 22:38:45 +08:00 via Android

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

waterlaw

2018-01-23 23:10:45 +08:00

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

```