B树和B+树数据结构以及B树在MySQL索引中的使用说明

一、二叉树到多叉树

1.二叉树的劣势
  • 二叉树每个节点至多只有两个子节点,如果整个数据比较大,那么我们的树的深度(高度)将非常大,无论对于插入或者删除,速度将会变得比较缓慢
2.多叉树(多路搜索树)

注:多叉树并不是专业的叫法,这里只是为了更好的理解

多路搜索树结构

M阶多路搜索树

  • 每个节点至多M个子节点

二、B树和B+树

1.B树即B-tree

注:这里的B是Balance

(1)B树的性质

B树又叫多路平衡查找树,其主要有以下几个性质:对于一个M阶的B树

  • 如果根节点不是叶子节点,那么它至少有2个子节点
  • 每个节点至多有M个子节点
  • 除了根节点和叶子节点外,其他节点至少有ceil(M/2)个节点
  • 非叶子节点如果有K个子节点,则有K-1个关键字(关键字就是每个节点有多个数据)
  • 所有叶子节点处于同一层
(2)B树的结构

B树本质上是一个多路搜索树,只不过,它的每个子节点,不是只有一项数据,而是有一批数据

3阶B树

注:这是一个3阶的B树

  • 至多有3个子节点
  • 比如包含[12, 14]这组数据的节点,有3个子节点,那它至多只能有2个关键字,即它至多只有有两个数据点
  • 3阶的B树的叶子节点,都在第3层中
(3)B树节点的插入
  • 节点的的插入为了满足B树的性质,需要做一些节点拆分

需要拆分的B树

  • 要向树中插入一个元素15,从根节点开始比较,插入的节点比根节点大,则应该插入到根节点的右子树上,依次比较,插入到叶子节点中,此时叶子节点为[9,10, 11, 15]个数据
  • 因为这是一个3阶的B树,所以,叶子节点最多只能3个数据,此时需要进行节点拆分
(4)B树节点的删除
  • 当删除非叶子节点时,为了满足B树的性质,也需要将节点做一些移动

需要移动节点的B树

(5)B树节点的查找
  • 从根节点开始,判断节点是在左子树还是右子树
  • 子节点的数值集合中通过二分法查找,如果在当前集合中查找到,则查找结束,如果没查找到,再在对应的子树中继续通过二分法查找
(6)B树节点内部结构

B树节点内部结构

  • 节点的key,相当于索引
  • 节点的data,具体存储的数据
  • 节点的前指针,指向比当前key小的子节点
  • 节点的后指针,指向比当前key大的子节点
(7)B树的存储结构

树的存储结构

2.B+树

相对于B树,B+树又增加了以下特征:

  • 叶子节点增加了指向下一个节点的指针 
  • 每个节点的指针上限为2d,则不是2d+1
  • 非叶子节点不存储具体数据,只存储key;叶子节点不存储指针

B+树的存储结构

三、在MySQL中通过B-Tree实现索引的解读

1.InnoDB存储引擎

InnoDB存储引擎,索引文件和数据文件在同一个文件

  • 叶子节点存储的是具体的数据
(1)主索引(主键索引)

InnoDB中的主索引

(2)辅助索引

InnoDB存储引擎中的辅助索引

  • 叶子节点存储的是主索引的key,需要通过主索引key来查找具体数据
2.MyISAM存储引擎
  • 主索引和辅助索引的叶子节点都是存储指向记录数据的指针,而不是数据
  • 辅助索引的叶子节点也是存储指向记录数据的指针,而不是指向主索引的指针

MyISAM存储引擎的索引