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

2018 年 1 月 23 日
 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 公里处的感觉,相信不少同行都有过这种体验。。。

不多说了,大家认为有何改进的地方,欢迎交流~
21847 次点击
所在节点    程序员
131 条回复
begeekmyfriend
2018 年 1 月 24 日
@fcten 没听说过一条记录一把锁的,底层只关注 node,你是不是没搞清楚概念?
fcten
2018 年 1 月 24 日
@begeekmyfriend
1、一万个线程竞争一把锁,这是一个并发,而不是一万个并发
2、可以搜索一下 mysql 的行级锁
begeekmyfriend
2018 年 1 月 24 日
@fcten 行级锁那是上层概念,底层怎么可能每一条记录上锁?
fcten
2018 年 1 月 24 日
@begeekmyfriend 不知道你的上层概念指的是什么,但是 mysql 行级锁是通过给索引的每一项上锁来实现的。
begeekmyfriend
2018 年 1 月 24 日
@fcten 就是上层的缓存啊,底层(包括我的 cache )指的是落地用的
fcten
2018 年 1 月 24 日
@begeekmyfriend 你给整个 cache 加锁了,那上层调用你的时候不一样被锁住了吗。上层做细粒度的锁还有什么意义……
Em5O7B1JGfjQnBry
2018 年 1 月 24 日
@begeekmyfriend 从数据库的角度考虑的话,只需要从索引中找出记录所属于的块,删掉就可以了,索引的 key 不需要处理,B+树有多余的 key 并不是什么问题,反正你顺着 key 往下找,发现记录不在了,那就是删掉了。考虑到实际的应用场景,其实数据库用到 delete 的操作非常非常少,大家在项目中都是维护一个 deleted 字段,删除就是把这个字段置为 1 就可以了。在极少数需要物理删除的情况,索引不删除 key,记录块不删除确实会造成膨胀的问题,发现有效记录过少的情况,直接重建就可以了。
huanghaofu86
2018 年 1 月 24 日
群主,想进入 BI 大数据行列,这路子,怎么走,有 3 年数据库开发经验
huanghaofu86
2018 年 1 月 24 日
@begeekmyfriend 楼主,是否可以交个朋友?
begeekmyfriend
2018 年 1 月 24 日
@huanghaofu86 我没有 DB 开发经验,全是业余作品
zhicheng
2018 年 1 月 24 日
实现一个不支持 variable size key 不支持 mvcc 不支持 acid 的单线程 B+tree 并不是什么难事(包括半分钟内写入 10M keys ),写了 3 年我不作评价。

在工程实践中,DELETE 命令删除的数据一般不是立即从 B+tree 中删除,大多是 mark delete,一是为了实现 MVCC,二是高并发涉及 merge 和 shift 的 delete 算法比较复杂。真正的删除往往是在 VACUUM 的时候批量删除。

并发 B+tree 有好几种方法,高性能的并发 B+tree 并不是像你想的那么简单,具体可以看相关论文了。

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://v2ex.ih06.com/t/425258

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX