B+Tree简介
基本概念
B+Tree是相比BTree的一种衍生体,最大的特点是叶子节点的数是通过链表进行关联起来
MySQL使用B+Tree的原因
Mysql是持久化的,数据和索引是存储在磁盘上的,每次的检索数据,需要从磁盘进行加载数据。磁盘的最小单位是扇区,扇区的大小只有512B的大小,操作系统通常一次会加载多个扇区的数据到内存中,操作系统最小的单位是块block,在Linux系统中block的大小通常为4KB,也就是说加载一个块的数据,默认是8个扇区的数据
每次的索引加载,都涉及到IO的操作,因为磁盘的IO越多,就会导致消耗的时间就会越长
满足MySQL的索引条件:
1、在尽可能少的IO中完成操作
2、要能高效的查找一个数据,也能高效的执行范围查找
B+Tree使用了二分查找,同时叶子节点为顺序排列,能够支持高效的范围查找
B+Tree的节点中只存储了索引数据,对于原data则存储在叶子节点中,更适合大量索引数据的检索;另一个重点是由于索引 文件都是存放在一个节点里面,对应相同的扇区,磁盘在进行预加载的时候,会把相邻的扇区的数据一起进行加载到内存中,这样在进行数据查找的时候更容易找到相邻扇区的索引数据,提升检索速度,减少了IO的操作
B+Tree特点
- 一棵M阶的树,每个分支节点,最多有M棵子树,比如一棵3三阶的树,每个分支节点最多只有三个子女
- 根节点最少两课子树
- 每个节点都包含n个元素,其中 m/2 <= n <= m
- 每个节点的元素大小都是从小到大依次排序
- 所有叶子节点都处于相同一层
- 每个叶子节点的元素大小都是从小到大依次排列,通过指针链接,形成有序链表
B+Tree的查找
B+Tree查找的时候,先去根节点找,然后会自上而下的进行查找,最终找到匹配的叶子节点,
比如查找51,在根节点中发现小于59,则继续在左边子树查找,依次发现比44大,比59小,则在59的子树中进行查找,定位到51(这里由于每一层的节点都是有序排列的,所以很容易定位到51具体在哪个子树上面)
B+树中间节点没有Data数据,所以同样大小的磁盘页可以容纳更多的节点元素。所以数据量相同的情况下,B+树比B树更加“矮胖“,因此使用的IO查询次数更少。
B+Tree的插入
- 所有的插入都是最终体现在叶子节点上面,且叶子节点的顺序是不能够被打乱的
- 如果插入的元素之后,当前节点的元素个数大于M,则需要对当前节点进行拆分处理,具体情况分为一下几类
- 如果当前节点插入了新元素之后,节点内的元素个数小于等于M,则不需要进行拆分处理
- 如果当前接插入新元素之后,节点内的元素个数大于M,则需要将当前节点拆分为左右两个节点,同时需要将原始节点里面的中间的元素,上升放置到父节点里面去,如下图,插入元素37:将37上升到父节点中,父节点中元素由[59,97]变为[37,59,97]
- 如果在第二步过程中,如果上移元素之后,父节点的元素个数大于M,则仍然需要进行元素拆分,方法跟第二步一样