B+超强树,带你知晓MySQL的底层是怎样的结构

B树

B-树(B树)

该树和B+树最大的区别在于,该树所有节点都存放数据.
学习之前,先弄清楚B树的特点:

1. M阶B树表示一个节点最多可以存放M个子节点
2. 每个节点最多有M-1个元素
3. 规定每个节点必须至少有两个子节点,且每个节点的元素按升序排列

B树在节点存储元素要知道的规则是: 连续存放元素一直要存到该节点最多能存放的数量为止,一旦超出了元素存放上限,先模拟出该存放的位置,然后将中间那个元素提升,如上图所示.
当我们为一个节点放满四个元素的时候,再放入53,因为是五阶树,再存放就不能存放了,只能先模拟存放在41和97之间,之后将该节点中间元素提升,也就是41,再讲剩下的节点分为该41节点的左子节点和右子节点.

B+树

B+树和B-树有两个区别: 非叶子节点只存放索引,通过该索引能索引到叶子节点,其次,叶子节点是用链表的结构存储的,这样子通过一个叶子节点就能找到其他叶子节点,不用再索引一次.

其插入数据的时候也和B-树如出一撤,只不过当节点元素满的时候,试讲节点的索引提上去.

应用

两种B树其实其实用得最多就是在磁盘IO上了,可以将每个节点看成一个磁盘块,然后就可以根据范围找到对应的磁盘进行刷盘,减少磁盘检索的次数.常见的MySQL底层就是使用B+树结构,之所以不用B-树,是因为B-树每个节点都存放数据,这样子如果要索引叶子节点的数据,得将该叶子节点前面所有节点都能走一遍,在这个走一遍的过程中,得拿出数据进行比较,才能根据范围查找到对应的磁盘,而在这个拿数据的过程中,就会产生刷盘的操作,这样为了找到叶子节点就增多了IO的次数.所以MySQL使用了B+树,不在非叶子节点上存放数据,而是存放能找到叶子节点的索引,叶子节点才是真正存放数据(MyISAM殷勤存放的也是索引),这样子我们每次索引叶子节点的时候就不用再去对非叶子节点进行刷盘,减少IO次数.