索引本质
    image.png
    数据结构可视化工具：
    https://www.cs.usfca.edu/~galles/visualization/Algorithms.html?url_type=39&object_type=webpage&pos=1

    1.二叉树
    二叉树特点是每个结点最多只能有两棵子树，只有左右之分，而且左边节点比父节点数据要小,右边节点比父节点数据要大。
    image.png
    二叉树结构图：
    image.png
    如图，如果mysql用二叉树进行索引设计的话，对于这种连续的数据进行查找数字7的话要从上往下依次查找，明显效率是很低的。

    2.红黑树
    红黑树也是一个二叉树，但它是一个二叉平衡树。
    二叉平衡树结构图：
    image.png
    由图可知，红黑树会对节点进行平衡处理，再找数字7的话3次就能找到了，效率是有所提升的，但是对于几十万甚至百万、千万级别数据表的时候，红黑树的树高度也会非常高，如果mysql用红黑树做索引的话依然是会存在查找低效率的问题。

    3.B-Tree
    B 树（Balance Tree）即为平衡树的意思。
    B树类似于红黑树，它与平衡二叉树不同的是平衡二叉树每个节点只存储一个键值和数据的，数据量大的情况下可以想象到二叉树的节点将会非常多，树高度也会极其高，查找数据时也会进行很多次磁盘 IO，为了解决平衡二叉树的这个弊端，我们应该寻找一种单个节点可以存储多个键值和数据的平衡树。也就是我们所说的B树。
    image.png
    B树结构图如下：
    image.png
    4.hash结构
    image.png