小白升级巨匠第1篇文章，开始写一些有深度的文章了

先举荐一个数据结构可视化工具网站，用于B+树可视化查看

Data Structure Visualizations

面试技术岗的时候，面试官问你：

mysql索引底层用的是B+树结构，为什么不必B树、二叉树、红黑树呢？

这里其实就是比拟各种数据结构的优劣点，最初阐明为什么要用B+树结构；

假如数据查问场景：当初有100W的数据存储，查问其中的一条，应该用哪种存储构造呢？

二叉查找树

二叉查找树即有序二叉树，满足二叉树的性质，具备上面特点：

  • 任意节点左子树不为空时，左子树值小于根节点值
  • 右子树不为空时，右子树值大于根节点值；

顺次存入数据，如果数据是递增的，则原二叉树进化为链表构造，如图

这种状况下，查问的工夫复杂度就是O(n)了

AVL树

AVL树即均衡二叉查找树，通过均衡因子差值判断是否均衡，再用旋转来实现树的均衡。左右子树的树高差不超过1。在执行插入删除操作时，对不满足条件的子树，通过旋转保持平衡。性能开销次要在旋转操作上，由此能够晓得AVL树适宜查问多，插入删除少的场景

如图，我创立了一棵AVL树，感兴趣的能够在网站上看一下插入过程和旋转调整均衡的过程。

AVL树须要维持树的均衡，而保护这种均衡的开销要大于取得的收益，理论利用中不多

红黑树

红黑树是一种二叉查找树，每个节点新增一个存储位标记是red或black，通过任何一条从根节点到叶子节点门路上，各个节点着色形式的限度，确保没有一条门路比其余门路长2倍，红黑树性质：

  • 根节点是彩色，每个节点非红即黑；
  • 叶子节点都是彩色
  • 如果一个节点是红色，那它的子节点都是彩色
  • 任意节点到叶子节点的门路都蕴含雷同数目的彩色节点

如图是红黑树的可视化：

AVL树和红黑树一样，随着记录数的减少，树的高度会一直减少，查问次数也会减少。

文章结尾咱们说的要查问100w条数据中的一条，就须要20次搜寻，搜寻效率不高，查问次数剖析如下

$$2^{20} = 1048576$$

B-树

即B树，和红黑树相比，B树的树高远远小于红黑树的高度。B树是为了和磁盘交互而设计的均衡多路查找树，操作效率有磁盘的拜访次数决定，树高越小，磁盘I/O工夫越短。

B树性质：

  • 非叶子节点上最多有M个子节点，且M>2；
  • 根节点的子节点数目为[2, M]；
  • 每个节点寄存至多M/2-1，至少M-1个关键字
  • 非叶子节点关键字数目=指向子节点的指针个数-1；
  • 所有叶子节点位于同一层

比照红黑树能够发现，每个节点上能够存储更多的数据，且树高固定，数据插入之后横向扩大。即每一次查问只须要搜寻3次就行。搜寻效率大大提高了。接着咱们再来看看B+树

B+树

说一下B+树的性质：

  • 非叶子节点的子树指针 和 关键字 个数一样；
  • 非叶子节点的子树指针，指向闭区间[k[i], k[i+1]]，即B树不容许关键字反复，B+树容许
  • 为所有叶子节点减少一个链指针；
  • 非叶子节点作为索引，叶子节点才存储关键字
  • 所有关键字存储在叶子节点

B+树比起B树的长处有：

  1. 只在叶子节点存储数据，16k的内存能够存下更多数据，升高树高
  2. 冗余索引，不便查找；
  3. B+树叶子节点减少了双向链表，不便范畴查问；

于是，回到结尾的问题，100W的数据，B+树只须要3次或4次I/O查问就能定位到了，且相比拟B树，B+树更适宜简单的查问场景，如范畴查问。