江苏龙网

  1. 首页 > 生活 > >

B+树咋在磁盘存储

谢邀！这个问题还是正合我意，因为我自己手把手亲自写了一个B+树最小demo，1K行的C代码，至今已有1K颗星，应该说代码得到了大众认可begeekmyfriend/bplustree
你问我怎么实现磁盘存储？我们还是先来看头文件，这里有核心数据结构的描述和接口签名：其中bplus_tree相当于一个handler，由调用接口的用户掌握。里面重要东西包括，文件描述符、节点缓存、根节点位置以及空洞节点链表。
typedef struct free_block { struct list_head link; off_t offset;} free_block;struct bplus_tree { char *caches; int used; char filename; int fd; int level; off_t root; off_t file_size; struct list_head free_blocks;}; 【B+树咋在磁盘存储】 文件描述符表明我的B+树是基于Posix接口实现，也就是说，最终面向用户磁盘存储形态是Unix文件，而不是裸机存储。
节点缓存是以内存缓存磁盘存储的节点，将磁盘存储的节点读取到内存，以便改动更新后，写回磁盘。实际上MIN_CACHE_NUM为5，也就是说我们最多需要五个节点大小的缓存足矣。
根节点位置是用来是B+树的搜索起点，它的值是文件中的偏移，注意根节点并非一定是文件最开始的地方，因为增删所以经常有变动。
空洞是指上次删除节点的标记，可用于下次新插入节点的位置，优先于追加。
除此之外，还有一些参数，比如节点大小block size（默认4KB）、非叶子节点的分支数目order、叶子节点的分支数目entries。
再来是节点数据结构。可以看到，我们用struct bplusnode表示通用节点，它有四个off_t成员，分别是自身位置、父节点位置和左右兄弟位置，位置表示文件中的偏移。再来是类型（叶子or非叶子），以及孩子数目，对于非叶子节点就是order的值，它的数目比key多一个，因为在增删中需要父子节点旋转；对于叶子节点，就是entry的值，同key的数目一样。
typedef struct bplus_node { off_t self; off_t parent; off_t prev; off_t next; int type; /* If leaf node, it specifies count of entries, * if non-leaf node, it specifies count of children(branches) */ int children;} bplus_node;/*struct bplus_non_leaf { off_t self; off_t parent; off_t prev; off_t next; int type; int children; key_t key; off_t sub_ptr;};struct bplus_leaf { off_t self; off_t parent; off_t prev; off_t next; int type; int entries; key_t key; long data;};*/在源码里我们只用到通用结构bplus_node，至于bplus_non_leaf和bplus_leaf是隐含的，在后面分析源文件时再说。
未完待续……

■网友
这个我也回答不来，建议读读MySQL源码吧

■网友
参考了一下另一个答案 @我的上铺叫路遥 的项目bplustree
还有一个go的内存版本bptree
我写了一个go版本的落盘b+树, 有兴趣的可以看一下
https://github.com/chainhelen/bptreeB+树的数据结构, 好多资料都是有一些微差异的,我是按照这篇 文章 的结构来的
===============
二更，除了上面提到的在master分支上实现了普通落盘版本，新增了transcation分支，避免在一次`insert/update/delete`过程中，部分节点修改失败，数据能够回滚能力.

■网友
可以参考我的实现（Go）：https://github.com/roy2220/plainkv#ordereddict （含数据结构图）


推荐阅读


上一篇：淘宝店铺几十万的流量，是咋做到的

下一篇：怎样评价魅族的售后