1K 行 C 写了 3 年，这是我从业以来写过的最烧脑的代码！
begeekmyfriend · begeekmyfriend · 2018-01-23 15:11:01 +08:00 · 19553 次点击这是一个创建于 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 公里处的感觉，相信不少同行都有过这种体验。。。
不多说了，大家认为有何改进的地方，欢迎交流~
从 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 和优化）。
第一，你得把 CRUD 全部实现再说；
第二对于其它版本，只要实现 bug free 就 OK 了，而我用 C 花的大部分时间是要把性能做到极致。
最关键的一点，我没做出一个 database 出来，这是很大的遗憾，因为光是这么一个 demo 估计很多人用不上。不过我日常实在也没多少精力了，要不然也不会花 3 年。有心人可以自己单干，不用 PR 给我了（除了 bug 和优化）。
 |
101
shaco 2018-01-24 10:35:31 +08:00
三年坚持一个 DEMO，值得尊敬！！
|
 |
102
skadi 2018-01-24 11:00:29 +08:00
@begeekmyfriend 具体的没测,但是高效肯定能做到啊.
|
 |
103
soli 2018-01-24 11:00:38 +08:00
|
 |
104
kylix 2018-01-24 11:35:36 +08:00
楼主精神可嘉，顶一下！
|
 |
105
jyf 2018-01-24 11:54:44 +08:00
如果是 kv 的话 可以考虑跟同领域的对比 也不一定非得是 sql 嘛 比如 sphia/wired tiger
|
 |
106
svenFeng 2018-01-24 11:59:37 +08:00 via Android
本来不想说的，，，看到 append 的内容，你是可以试着实现一下并发的 B+tree，并且不再是一个独立的数据结构，而是作为整个带事务的数据库的一部分，就知道为什么不实现删除操作也是合理的了。
|
 |
107
begeekmyfriend OP @svenFeng 删除和插入本质都是一样的写操作而已，怎么并发就不能实现了？
|
 |
108
hugee 2018-01-24 13:09:38 +08:00 via Android
大师
|
|
109
svenFeng 2018-01-24 13:13:06 +08:00 via Android
@begeekmyfriend 不是不能，而是考虑到性能和删除会引发一系列问题，代价太大完全不合算的，你可以看看 B-link tree，并发 B+树的一种变种，说不定就能理解这种权衡了
|
 |
110
jsfaint 2018-01-24 13:16:45 +08:00
给楼主点赞！
|
 |
111
ahonn 2018-01-24 13:20:30 +08:00
牛，虽然看不太懂。但是这个 1k 行代码能写 3 年就已经很了不起了。专研精神 Max
|
 |
112
frend94 2018-01-24 14:25:02 +08:00
看了 lzGitHub，大佬哇
|
|
113
begeekmyfriend OP @svenFeng 粗略浏览了一下 B-link，传说中的分布式索引？有文章证明了插入和查询线程之间的并发正确性，那是因为插入只会分裂新的节点，新分裂的节点不存在引用关系，故而可以避免竞态。而删除则会导致合并，对于已存在引用关系的节点，则必然导致竞态。故而只能用全局锁，对每一个 CRUD 操作加锁，就会损失性能，是这个意思吧？我很好奇如果没有删除，那么废弃的 key 怎么处理？
|
|
114
begeekmyfriend OP @svenFeng 对于我目前实现的 B+树来说，实现插入 /查询的并发并非什么难事，我一共只用到 MIN_CACHE_NUM=5 个内存映射 node cache，对每一个 cache 加锁就可以了。
|
 |
115
fcten 2018-01-24 14:48:32 +08:00
@begeekmyfriend 给 cache 加锁就是全局锁，插入、查询不应该使用全局锁
|
|
116
begeekmyfriend OP @fcten 不是吧，一个 cache 对应一个 node 啊，只是在操作内部引用 cache 的时候才上锁。全局锁指的是整个 tree 用一把锁，这才是对 CRUD 操作上锁。
|
|
117
begeekmyfriend OP @fcten 不同 cache 对应的 node 如果不存在引用关系，那么就不存在竞态问题和互斥处理
|
|
118
fcten 2018-01-24 14:53:16 +08:00
@begeekmyfriend 你不是说只有 5 个 cache 吗，那就是对应 5 个锁了？我不清楚你的具体实现，你这样能做到 5 个以上的并发吗？
|
|
119
fcten 2018-01-24 14:56:15 +08:00
@begeekmyfriend 而且，你的 node 对应了很多记录吧。理论上最优的话应该是操作某个记录就只给这个记录加锁。对整个 block 加锁会锁住很多无关的记录
|
|
120
begeekmyfriend OP @fcten
1、cache 数目跟线程数目有关系吗？ 1W 个线程引用 cache A，只会用一把锁互斥啊 2、cache A 的锁又不会给 cache B 上锁，这在分裂新节点情况下是不存在竞态的。 |
|
121
begeekmyfriend OP @fcten 没听说过一条记录一把锁的，底层只关注 node，你是不是没搞清楚概念？
|
|
122
fcten 2018-01-24 15:00:59 +08:00
|
|
123
begeekmyfriend OP @fcten 行级锁那是上层概念，底层怎么可能每一条记录上锁？
|
|
124
fcten 2018-01-24 15:08:15 +08:00
@begeekmyfriend 不知道你的上层概念指的是什么，但是 mysql 行级锁是通过给索引的每一项上锁来实现的。
|
|
125
begeekmyfriend OP @fcten 就是上层的缓存啊，底层（包括我的 cache ）指的是落地用的
|
|
126
fcten 2018-01-24 15:18:30 +08:00
@begeekmyfriend 你给整个 cache 加锁了，那上层调用你的时候不一样被锁住了吗。上层做细粒度的锁还有什么意义……
|
|
127
svenFeng 2018-01-24 15:21:30 +08:00
@begeekmyfriend 从数据库的角度考虑的话，只需要从索引中找出记录所属于的块，删掉就可以了，索引的 key 不需要处理，B+树有多余的 key 并不是什么问题，反正你顺着 key 往下找，发现记录不在了，那就是删掉了。考虑到实际的应用场景，其实数据库用到 delete 的操作非常非常少，大家在项目中都是维护一个 deleted 字段，删除就是把这个字段置为 1 就可以了。在极少数需要物理删除的情况，索引不删除 key，记录块不删除确实会造成膨胀的问题，发现有效记录过少的情况，直接重建就可以了。
|
 |
128
huanghaofu86 2018-01-24 15:53:44 +08:00
群主，想进入 BI 大数据行列，这路子，怎么走，有 3 年数据库开发经验
|
|
129
huanghaofu86 2018-01-24 15:54:28 +08:00
@begeekmyfriend 楼主，是否可以交个朋友？
|
|
130
begeekmyfriend OP @huanghaofu86 我没有 DB 开发经验，全是业余作品
|
 |
131
zhicheng 2018-01-24 16:27:34 +08:00
实现一个不支持 variable size key 不支持 mvcc 不支持 acid 的单线程 B+tree 并不是什么难事（包括半分钟内写入 10M keys ），写了 3 年我不作评价。
在工程实践中，DELETE 命令删除的数据一般不是立即从 B+tree 中删除，大多是 mark delete，一是为了实现 MVCC，二是高并发涉及 merge 和 shift 的 delete 算法比较复杂。真正的删除往往是在 VACUUM 的时候批量删除。 并发 B+tree 有好几种方法，高性能的并发 B+tree 并不是像你想的那么简单，具体可以看相关论文了。 |
Select Language