回顾我们学习的线性和课扩展哈希 他们都只能进行等值操作 但是不能进行区间操作 为了进行区间操作和关系的比较和速度考虑 引入数据结构B+树
序言:磁盘存储
1. mysql面试题-深入理解B+树原理_哔哩哔哩_bilibili
信息是存取在磁盘块中的每个 磁盘最小的存取单位是512KB 要定位磁盘某一个区域 需要通过是确定扇区和磁道 虽然绿色的位置比 外圈的短但是存储信息的容量是相等的。
以这个为例 磁盘大概需要500个扇区。
通过不断建立索引之后减少了IO的次数
结构特点
B+树的数据结构
等值查找 & 区间查找
区间查询 先利用下节进行一次查找然后沿着根节点指向的链表进行区间查询
B树的插入
引入middel key这个概念
插入理想的情况:
插入不理想的情况:
以插入15为例 首先先找到15需要插的位置 此时发现 13 15 17 19已经装不下了, 此时将13 15 17两段 生成一个middel key 17 23始终指向 block 17 19
删除索引项
顺利的话 他就是半满的情况很简单
不顺利 需要使用节点合并策略;
可以向兄弟借指针
树可视化工具
B+ Tree Visualization (usfca.edu)
压缩存储
前缀压缩
后缀截断:
只需要前几个的字母就可以了 不需要后面的字母所以后边的字母直接截断。
批量加载
当分裂的节点不够的时候， 需要进行拆解
如图所示进行结果的分裂
