MySQL的索引是在存储引擎层实现的，不同的存储引擎有不同的结构，主要包含以下几种：

    image.png

    索引结构在不同的引擎中的支持情况
    image.png

    我们平常所说的索引，如果没有特别指明，都是指B+树结构组织的索引。

    ⚫ 二叉树
    一个节点下最多包含2个子节点，父节点的子节点相对于父节点左小右大
    image.png

    二叉树缺点：顺序插入时，会形成一个链表，查询性能大大降低。 大数据量情况下，层级较深，检索速度慢。
    image.png
    为了规避二叉树的顺序插入的缺点，引入了另一种数据结构
    红黑树：为了规避二叉树的顺序插入的缺点，大数据量情况下，层级较深，检索速度慢。
    image.png
    思考：2个子节点会导致层级很深，检索速度慢，我们能不能构建多个子节点呢？

    ⚫ B-Tree（多路平衡查找树）
    以一颗最大度数（max-degree）为5(5阶)的b-tree为例(每个节点最多存储4个key，5个指针)：
    度数=指针=key+1;

    image.png
    注意: 树的度数指的是一个节点的子节点个数。

    image.png
    课堂案例：
    插入 100 65 169 368 900 556 780 35 215 1200 234 888 158 90 1000 88 120 268 250 数据为例。
    image.png

    ⚫ B+Tree
    以一颗最大度数（max-degree）为4（4阶）的b+tree为例：
    image.png
    特点：所有的元素都会出现在子节点，分叶子节点只起到索引的作用，叶子节点形成一个单向链表。
    插入 100 65 169 368 900 556 780 35 215 1200 234 888 158 90 1000 88 120 268 250 数据为例。
    演示链接：https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

    image.png
    相对于B-Tree区别:
    ①. 所有的数据都会出现在叶子节点
    ②. 叶子节点形成一个单向链表

    MySQL索引数据结构对经典的B+Tree进行了优化。在原B+Tree的基础上，增加一个指向相邻叶子节点的链表指针，就形成了带有顺 序指针的B+Tree，提高区间访问的性能。

    image.png

    ⚫ Hash
    哈希索引就是采用一定的hash算法，将键值换算成新的hash值，映射到对应的槽位上，然后存储在hash表中。如果两个(或多个)键值， 映射到一个相同的槽位上， 他们就产生了hash冲突（也称为hash碰撞）， 可以通过链表来解决。

    例如下图：为name字段创建hash索引的过程：
    1.先算出每一行数据的hash值——>2.拿到name字段的所有值，针对name字段的所有值，通过内部的hash函数计算每一个name映射的槽位——>3.那么在对应槽位中就会存储key=name,value=key对应的行所对应的hash值
    image.png

    ➢ Hash索引特点
    1. Hash索引只能用于对等比较(=，in)，不支持范围查询（between，>，< ，…）
    2. 无法利用索引完成排序操作
    3. 查询效率高，通常只需要一次检索就可以了，效率通常要高于B+tree索引
    ➢ 存储引擎支持
    在MySQL中，支持hash索引的是Memory引擎，而InnoDB中具有自适应hash功能，hash索引是存储引擎根据B+Tree索引在指定条件下自动构建的。

    思考：
    image.png

    为什么InnoDB存储引擎选择使用B+tree索引结构，而没有选择：二叉树、B-tree、Hash?

    ➢ 相对于二叉树，层级更少，搜索效率高；
    ➢ 对于B-tree，无论是叶子节点还是非叶子节点，都会保存数据，这样导致一
    页中存储的键值减少，指针跟着减少，要同样保存大量数据，只能增加树的
    高度，导致性能降低；
    ➢ 相对Hash索引，B+tree支持范围匹配及排序操作；