V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
begeekmyfriend
V2EX  ›  程序员

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

  begeekmyfriend ·
begeekmyfriend · 2018-01-23 15:11:01 +08:00 · 19549 次点击
这是一个创建于 2480 天前的主题,其中的信息可能已经有所发展或是发生改变。
就这么一个数据结构玩意儿,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 和优化)。
131 条回复    2018-01-24 16:27:34 +08:00
1  2  
wangmm
    1
wangmm  
   2018-01-23 15:13:21 +08:00   ❤️ 1
厉害 程序小白摩拜!
hahasong
    2
hahasong  
   2018-01-23 15:14:49 +08:00 via iPhone   ❤️ 1
程序小白 OFO
Applenice
    3
Applenice  
   2018-01-23 15:17:52 +08:00   ❤️ 1
程序小白 小蓝
allen6699
    4
allen6699  
   2018-01-23 15:19:43 +08:00
程序小白 滴滴
xjr1022
    5
xjr1022  
   2018-01-23 15:20:37 +08:00
程序小白 滴滴
Ethous
    6
Ethous  
   2018-01-23 15:22:29 +08:00 via Android
一件事,能坚持做三年。这种毅力值得点赞!
stoldog
    7
stoldog  
   2018-01-23 15:23:27 +08:00   ❤️ 1
程序小白 HelloBike
zorui
    8
zorui  
   2018-01-23 15:26:00 +08:00   ❤️ 1
程序小白 小鸣
xntop
    9
xntop  
   2018-01-23 15:36:14 +08:00
关键是视机器而定,哈哈
jzds001
    10
jzds001  
   2018-01-23 15:37:27 +08:00
赞坐
owenliang
    11
owenliang  
   2018-01-23 15:46:18 +08:00
红黑书与 B 树是我从来没试图写过的数据结构,虽然后面 K/V 时代出现了更多牛逼的树,但都很难!
ZyZyZzz
    12
ZyZyZzz  
   2018-01-23 15:46:37 +08:00 via Android   ❤️ 9
@Livid 这是一个极好的主题贴,然而你来看看我楼上都回复了些什么
ynyounuo
    13
ynyounuo  
   2018-01-23 15:52:20 +08:00   ❤️ 33
恭喜你,你的心里有了 B 树
jadec0der
    14
jadec0der  
   2018-01-23 15:52:41 +08:00
lz 牛逼啊,这么有耐心,佩服佩服
Applenice
    15
Applenice  
   2018-01-23 15:55:12 +08:00
去点了 star~~~
wowo243
    16
wowo243  
   2018-01-23 15:56:39 +08:00 via Android
我是来看回复的。。。
luckychenhaha
    17
luckychenhaha  
   2018-01-23 16:01:23 +08:00
666,先 star 为敬
jecshcier
    18
jecshcier  
   2018-01-23 16:08:20 +08:00 via iPhone
看回复来的。。。
codexu
    19
codexu  
   2018-01-23 16:12:36 +08:00
给大佬递 star
soli
    20
soli  
   2018-01-23 16:13:11 +08:00
不来个横向对比么?
比如和 Redis、MySQL 等对比一下性能?
linxl
    21
linxl  
   2018-01-23 16:13:32 +08:00
不知道你在说什么, 但是我也会摩拜
kaiser1992
    22
kaiser1992  
   2018-01-23 16:15:30 +08:00
有必要把 benchmark 测试结果贴出来
supercaizehua
    23
supercaizehua  
   2018-01-23 16:16:59 +08:00 via Android
程序小白 哈罗
scriptB0y
    24
scriptB0y  
   2018-01-23 16:24:25 +08:00
程序小白 捷达
begeekmyfriend
    25
begeekmyfriend  
OP
   2018-01-23 16:28:06 +08:00
@kaiser1992 IO 的东西跟机器相关,做不到很公正吧
begeekmyfriend
    26
begeekmyfriend  
OP
   2018-01-23 16:29:14 +08:00
@soli Redis 和 MySQL 两者之间对比都是不公正的
loading
    27
loading  
   2018-01-23 16:30:59 +08:00
滴 幼儿票
zxybird
    28
zxybird  
   2018-01-23 16:36:20 +08:00
点个 star,予以支持
dobug
    29
dobug  
   2018-01-23 16:43:08 +08:00
点赞
YouXia
    30
YouXia  
   2018-01-23 16:46:06 +08:00
赞!
Andiry
    31
Andiry  
   2018-01-23 16:47:24 +08:00
初看了一下有问题啊,node_flush()里只有 pwrite 没有 fsync,如何能保证数据落到磁盘呢?支持 failure recovery 吗?
begeekmyfriend
    32
begeekmyfriend  
OP
   2018-01-23 16:51:53 +08:00
@Andiry 还没做到这一步
cnwtex
    33
cnwtex  
   2018-01-23 16:54:51 +08:00
没有一个 issue, 这种东西有人在用吗?
Andiry
    34
Andiry  
   2018-01-23 16:55:28 +08:00
@begeekmyfriend 那样的话这个性能测试没啥意义了,因为本质还是内存版本。
begeekmyfriend
    35
begeekmyfriend  
OP
   2018-01-23 16:57:01 +08:00
@Andiry 因为我还没想好怎么加,最笨的方法,你直接在 write 后面 sync 再测一下呗,慢不了的
begeekmyfriend
    36
begeekmyfriend  
OP
   2018-01-23 16:58:26 +08:00
@cnwtex 我关闭了,另外,老外都 email 了
cnwtex
    37
cnwtex  
   2018-01-23 17:02:15 +08:00
@begeekmyfriend 不好意思, 没做过开源项目. 都 email 的话, 是你的客户吧?
我搂了一眼, 暂时用不上, 加油!
begeekmyfriend
    38
begeekmyfriend  
OP
   2018-01-23 17:05:03 +08:00   ❤️ 1
@cnwtex 据我所知,star 的好多都是前端的,估计不想用数据库。。。
anubiskong
    39
anubiskong  
   2018-01-23 17:06:09 +08:00
现在时代这么浮躁,难得有你这么坚持做一件事的人,加油
JanKinAn
    40
JanKinAn  
   2018-01-23 17:10:50 +08:00 via Android
我默默的删掉了我的 gayhub 库
duesicilie
    41
duesicilie  
   2018-01-23 17:36:25 +08:00
滴!发生了什么?这不是个上班时间灌水用的地儿吗
exch4nge
    42
exch4nge  
   2018-01-23 17:44:37 +08:00
在精神上支持 LZ。不过不知道什么场景下会用 LZ 这种库,生产环境下 leveldb 是更好的一种选择吧。
begeekmyfriend
    43
begeekmyfriend  
OP
   2018-01-23 17:48:21 +08:00
@exch4nge 本来是想写个 database 的,但按照进度估计写不动了,做到这地步,交接给有缘人吧
zpf124
    44
zpf124  
   2018-01-23 17:50:35 +08:00
只能称赞一句,但我技术差太多而且没有什么毅力估计没法模仿大佬的历程。
zouqiang
    45
zouqiang  
   2018-01-23 17:55:24 +08:00
膜拜
fcten
    46
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
    47
begeekmyfriend  
OP
   2018-01-23 18:03:38 +08:00
@fcten 你给 block_size 设置了一个多大的数?
fcten
    48
fcten  
   2018-01-23 18:06:37 +08:00   ❤️ 1
@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
    49
skadi  
   2018-01-23 18:20:52 +08:00
如果只是数据结构的话,大学的时候 b 树以及几个变种自己都手动实现过.并不觉得...
chenweidong
    50
chenweidong  
   2018-01-23 18:24:21 +08:00
吊就一个字,我只说一次。
daozhihun
    52
daozhihun  
   2018-01-23 18:29:50 +08:00 via Android
歪个楼,楼主的头像我第一眼看以为是刑舅舅 😂
begeekmyfriend
    53
begeekmyfriend  
OP
   2018-01-23 18:35:00 +08:00
@skadi 半分钟内插入 1KW 个 key 再说,不然就是假的 B 树
acros
    54
acros  
   2018-01-23 18:45:45 +08:00
捂着脸说一句:我看不懂(其实也压根没看,B+树磁盘存储 CRUD 几个关键字好像离我很远)。

能搭配开发博客看就好了,或者随便写写开发心得啊。
比如 rapidjson 的这个做法,博客比代码容易引流嘛:
https://github.com/Tencent/rapidjson
https://zhuanlan.zhihu.com/p/20029820
hsuan
    55
hsuan  
   2018-01-23 19:08:34 +08:00 via Android
挺好的,不过想不到有啥用
stabc
    56
stabc  
   2018-01-23 19:11:11 +08:00
既然说了“视机器而定”,为什么不把你的性能测试的机器硬件贴出来呢?
closedevice
    57
closedevice  
   2018-01-23 19:16:33 +08:00
不错,加油
0915240
    58
0915240  
   2018-01-23 19:20:19 +08:00
给大佬端茶倒水
jeffciu
    59
jeffciu  
   2018-01-23 19:22:43 +08:00 via iPhone
没仔细研究过 B+树,但还是佩服楼主的成果
likuku
    60
likuku  
   2018-01-23 19:24:10 +08:00
1K 行能写这种底层硬功能,也真是了不起!
feng32
    61
feng32  
   2018-01-23 19:31:48 +08:00 via Android
赞一个
因为业务关系,我现在只记得 k-d 树的写法了
begeekmyfriend
    62
begeekmyfriend  
OP
   2018-01-23 19:32:39 +08:00
@feng32 KD 树我也有,要不要 PK 一下: https://github.com/begeekmyfriend/kdtree
begeekmyfriend
    63
begeekmyfriend  
OP
   2018-01-23 19:34:30 +08:00
@stabc 懒得贴了,thinkpad t440,后面没字母
unique
    64
unique  
   2018-01-23 19:37:09 +08:00 via iPhone
为楼主的坚持点赞👍🏾
rashawn
    65
rashawn  
   2018-01-23 20:37:48 +08:00 via iPhone
为啥 trending 上有个一样名字的项目 但不是楼主写的 好奇怪
rashawn
    66
rashawn  
   2018-01-23 20:39:04 +08:00 via iPhone
rashawn
    67
rashawn  
   2018-01-23 20:41:01 +08:00 via iPhone
感觉你们两个是有缘人
begeekmyfriend
    69
begeekmyfriend  
OP
   2018-01-23 21:26:41 +08:00
@rashawn 你看他 issue,没实现删除,骗 star 来着~
begeekmyfriend
    70
begeekmyfriend  
OP
   2018-01-23 21:33:59 +08:00
@acros 人家那是正式发布到很多版本后才写博客的,我连个 database 都没力气写了
letianqiu
    71
letianqiu  
   2018-01-23 21:56:03 +08:00
正好在看 B 树,有个问题没有懂,想请教。B 树究竟如何减少磁盘 I/O ?如果 B 树节点里有记录储存在硬盘里的实际地址,那么这个地址是怎么得到的?在写文件之前应该是拿不到实际地址的?如果写完才能拿到,那么是不是再将地址写入?
begeekmyfriend
    72
begeekmyfriend  
OP
   2018-01-23 22:07:03 +08:00
@letianqiu 我写的是 B+树。
如果要减少磁盘 I/O 那么尽量一个节点容纳多个索引,索引节点越少,读操作 I/O 次数越少,查询越快,但也不能太多,否则插入删除就需要相关子节点全部更新,这就是为什么 B 树的写效率偏低。
我是基于 POSIX 实现的,不是裸机,所以存储的是文件,实际地址自然是文件字节偏移,后面该如何处理你应该明白
HaoyangWei
    73
HaoyangWei  
   2018-01-23 22:19:28 +08:00
滋瓷~
佩服楼主的毅力
szhaoliang
    74
szhaoliang  
   2018-01-23 22:38:45 +08:00 via Android
都坚持三年了再坚持一下,当初我就是打算做一下别的放松放松再回来,结果现在就只能给大佬倒茶水了......
waterlaw
    75
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':

```
wujunze
    76
wujunze  
   2018-01-23 23:22:27 +08:00
大神 厉害了 观摩一下代码
begeekmyfriend
    77
begeekmyfriend  
OP
   2018-01-23 23:28:46 +08:00
@waterlaw 你这是 clang 吧,还是 demo 测试里的,我没有在 switch-case 里用 break,有意为之,编译选项过于严格了。
Rorysky
    78
Rorysky  
   2018-01-23 23:37:19 +08:00
有毅力,观摩学习下代码~
crayhuang
    79
crayhuang  
   2018-01-23 23:50:23 +08:00
膜拜~
bigeast
    80
bigeast  
   2018-01-24 00:01:21 +08:00
巧了,今天在 hacker news 上看到一条推送,也是一个 B+树,名字都一模一样,https://github.com/NicolasLM/bplustree

不过是用 python 写的。
begeekmyfriend
    81
begeekmyfriend  
OP
   2018-01-24 00:03:45 +08:00 via Android
@bigeast 那个还没有删除操作
deali
    82
deali  
   2018-01-24 00:32:57 +08:00 via Android
默默点赞
caola
    83
caola  
   2018-01-24 02:28:26 +08:00
程序小白 优拜
Dxer
    84
Dxer  
   2018-01-24 07:34:25 +08:00 via Android
只能默默地为你点赞
Michaelssss
    85
Michaelssss  
   2018-01-24 07:47:05 +08:00
默默点赞
jadeity
    86
jadeity  
   2018-01-24 08:28:20 +08:00
@ZyZyZzz 现在再看看楼下
TreStone
    87
TreStone  
   2018-01-24 08:37:04 +08:00
楼主代码风格真是漂亮,打算将楼主 B+树移植到嵌入式平台,目前有一处不是很明白,“ struct free_block ”作用是什么?烦请楼主解惑。
silianbo
    88
silianbo  
   2018-01-24 08:41:48 +08:00
mark
begeekmyfriend
    89
begeekmyfriend  
OP
   2018-01-24 08:43:57 +08:00
@TreStone 那是删除后留下的空节点,可供后来者插入
lxrmido
    90
lxrmido  
   2018-01-24 08:57:18 +08:00
学习一下,膜拜
shiyouming91
    91
shiyouming91  
   2018-01-24 09:00:25 +08:00 via iPhone
楼主厉害 这个可能也有参考价值 http://www.lmdb.tech/doc/index.html
wsb200514
    92
wsb200514  
   2018-01-24 09:16:03 +08:00
膜拜
iamnoten
    93
iamnoten  
   2018-01-24 09:27:30 +08:00
厉害
bojackhorseman
    94
bojackhorseman  
   2018-01-24 09:29:45 +08:00
@daozhihun #52 团座大人
bojackhorseman
    95
bojackhorseman  
   2018-01-24 09:31:57 +08:00
@daozhihun #52 啊,错了,是师座。
nuanyang
    96
nuanyang  
   2018-01-24 09:45:10 +08:00 via iPhone
膜拜
hasbug
    97
hasbug  
   2018-01-24 09:48:03 +08:00
程序小白 嘟嘟
cstj0505
    98
cstj0505  
   2018-01-24 09:48:26 +08:00
佩服 lz 的坚持
zchzch1014
    99
zchzch1014  
   2018-01-24 09:57:45 +08:00 via iPhone
楼主做的事就像自己的名字一样,敬佩
hellboys
    100
hellboys  
   2018-01-24 10:01:36 +08:00
我感觉楼主更牛逼的是这个哈
https://github.com/begeekmyfriend/leetcode
1  2  
关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5024 人在线   最高记录 6679   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.5 · 98ms · UTC 03:52 · PVG 11:52 · LAX 19:52 · JFK 22:52
Developed with CodeLauncher
♥ Do have faith in what you're doing.