B+树实现磁盘存储

[begeekmyfriend]

三年前我就想写一个关系数据库了，无奈却苦于 B+树算法的实现，如今数据库仍旧没着落，但总算写出 B+树实现了磁盘落地。虽然只是个 demo ，但算法上保证完备，实践上经久耐操，对百万级样本处理达到秒级性能。附上源码以及测试用例（包括文件落地和读写），望数据库和存储大牛们切磋指教！

https://github.com/begeekmyfriend/bplustree

一种玩法： 随机生成一百万样本和四百万条 CRUD 指令，将结果存储到/tmp/data.bp和/tmp/metadata.bp中

./coverage_build.sh

退出后再次运行 demo ，读取默认保存的/tmp/data.bp和/tmp/metadata.bp

./demo_build.sh

使用 dump 指令在终端上画出整个树形结构（见 help 输出）

注意：下次玩的时候记得更改文件名，否则会把文件中原有的数据读入

顺便说一句，代码质量基本属于principle(al)级别，电脑搞坏我全陪！

[shoaly]

样本在哪里?

[shoaly]

sorrry...........眼睛太瞎 找到了

[Em5O7B1JGfjQnBry]

。。。 B+树的索引有这么难么。。。感觉就是细节比较多吧

[micyng]

大概 1 个月前验证过楼主的代码，跟 http://www.cs.usfca.edu/~galles/visualization/BPlusTree.html 结果稍微有些不一样

[Em5O7B1JGfjQnBry]

丢一个自己写的垃圾 rdbms[sdb]( https://github.com/svenFeng/sdb/blob/master/readme.md)（逃

[Em5O7B1JGfjQnBry]

链接错了😂😂😂https://github.com/svenFeng/sdb

[wlee1991]

我不会再给任何公司工作。我会创造一个伟大的公司，它会创造世界上最精致的产品，它会给真正有价值的人相应的回报和尊重。

seriously ？？？

[lbp0200]

可以实现 nosql ，比如 key 、 value

[begeekmyfriend]

@micyng 主要还是节点分裂点的选择不一样，比如我一向是(len + 1) / 2 ，而他则有时这样，有时又是 len / 2 ，导致结构不一样，但不影响效果和效率。另外我仍然保留了内存版，你可以观察效果，并且随意设置节点大小，比如把叶子设置得比非叶子更大一点： https://github.com/begeekmyfriend/bplustree/tree/in-memory

[begeekmyfriend]

@lbp0200 nosql 原本不需要 B+树，你看 redis 实现过吗？ B+树本来就是为 SQL 实现的，它比 B 树的优势在于范围查询更快，因为数据都在叶子节点上，所有的叶子节点又在同一底层上

[begeekmyfriend]

我在一篇博文 http://www.yinwang.org/blog-cn/2017/04/17/management-tricks 写到：“索引的存储又分为有序和无序，前者使用关联式容器，比如 B 树，后者使用哈希算法。这两类算法各有优劣：比如，关联式容器时间复杂度稳定 O(logN)，且支持范围查询；又比如哈希算法的查询、增删都比较快 O(1)，但这是在理想状态下的情形，遇到碰撞严重的情况，哈希算法的时间复杂度会退化到 O(n)。”

显然 nosql 一般使用的都是哈希一类数据结构，也可以用关联式容器，但从性价比上看，哈希表是最高的。

[begeekmyfriend]

抱歉，上楼链接放错了， V2EX 不支持删除啊： http://coolshell.cn/articles/17225.html

[artandlol]

“电脑搞坏我全陪 ” 好可怕 直男不好这口

[AngelCriss]

你这个有内存泄漏啊

[begeekmyfriend]

@AngelCriss 请给出证据，我使用 valgrind 跑过的

[begeekmyfriend]

@AngelCriss 抱歉，你应该指的是我今天 fix 的提交： https://github.com/begeekmyfriend/bplustree/commit/a3a064220d22c690d84ced9af3d077dc9a90dba9

[ccl]

楼主莫非是王垠？久仰呀

[wangjie]

@ccl 不是吧， 11L 的链接放错了，下面那个文章才是 lz 的

[sunny123]

楼主，你好，请问我打算 key 放手机号，用了 long 类型的数据类型输出还是错误，没法正常输出正常的手机号，unsigned long 好像只能输出最大值，代码有些地方还是看不太懂，key 放数组型进行比较是不是比较麻烦，能不能请楼主指导一下

[begeekmyfriend]

@sunny123 抱歉回复晚了，应该可以的，你打算用定长还是变长数组？

[sunny123]

@begeekmyfriend 好久没来了，感谢回复，问题已解决，用的 string 形式的 key

[begeekmyfriend]

@sunny123 用 C++写的么，发展的怎样了，前端用了 SQL 没:-)