索引底层原理

在mysql中，数据的存储形式与索引的射击，决定了mysql的数据检索功能

索引的作用：数据的快速检索

索引的本质：合适的数据结构

底层数据结构

假定现在有一个user表，里面有个七个数据，主键id从1~7

• 哈希表

  • 哈希算法：也叫散列算法，就是把任意值通过哈希函数变化为固定长度的地址，通过这个地址进行具体数据存储的数据结构
  • 例子：
    • 现在检索id=7的数据
      • select * from user where id = 7；
      • 先计算存储id=7的数据的物理地址 hash(7) =0X77
      • 根据地址0X77找到对应的数据
  • 可能遇到问题：哈希冲突
    • 哈希冲突是指，不同的key值，可能通过哈希函数转化后，出现相同的结果
      • 例如hash(7) 与 hash(199)
    • 常用的解决方式是链地址法。就是计算完哈希值后，还要检查一下数据是否相同，如果不同，则使用链表把冲突的两个数据连接起来
  • mysql没有采用这个算法
    • select * from user where id >3
    • 在进行上面这种模糊查询的时候，范围查找如果使用哈希算法的话，应该怎么做？
      • 简单的处理方式就是一次性把所有数据先读取出来，在筛选数据。很明显效率很低

• 二叉查找树(BST)

  • 数据结构：树节点，比父节点小的放左边，比父节点大的数放右边 如下图：

    
    
    1598658243337.png

• 能否实现哈希算法不能提供的范围查找：

  • 能，二叉树的叶子节点都是按序排列的，从左到右依次升序排列，如果我们需要找 id>5 的数据，那我们取出节点为 6 的节点以及其右子树就可以了

• 缺点：

  • 极端情况下会退化成链表，二分查找也会退化为遍历查找，检索性能大大下降。比如下面这个图：

1598658384890.png

  和上面的结构不一样，这个数据如果需要检索id=7的数据，则需要计算7次了

• mysql没有采用这个算法

• AVL树与红黑树

  • 二叉查找树存在不平衡问题，因此学者提出通过树节点的自动旋转和调整，让二叉树始终保持基本平衡的状态，就能保持二叉查找树的最佳查找性能了。基于这种思路的自调整平衡状态的二叉树有 AVL 树和红黑树。

  • 红黑树：

    • 这是一颗会自动调整树形态的树结构，比如当二叉树处于一个不平衡状态时，红黑树就会自动左旋右旋节点以及节点变色，调整树的形态，使其保持基本的平衡状态（时间复杂度为 O（logn）），也就保证了查找效率不会明显减低。比如从 1 到 7 升序插入数据节点，如果是普通的二叉查找树则会退化成链表，但是红黑树则会不断调整树的形态，使其保持基本平衡状态，如下图所示。下面这个红黑树下查找 id=7 的所要比较的节点数为 4，依然保持二叉树不错的查找效率。

    • 红黑树是针对AVL树维持平衡开销大, 在防止退化与调节平衡开销之间做的取舍.

1598658545280.png

- mysql没有采用这个算法

  - 当数据插入时，会出现这样一种情况，数据库主键id是自增的，顺序插入数据的时候，可能会导致红黑树处于右倾的状态。此时查询时候，会多出很多等待时间

  - 磁盘io操作太多

1598658669025.png

• 自平衡二叉树 AVL 树。 AVL 树是个绝对平衡的二叉树

  • AVL 树顺序插入 1~16 个节点，查找 id=16 需要比较的节点数为 4。从查找效率而言，AVL 树查找的速度要高于红黑树的查找效率（AVL 树是 4 次比较，红黑树是 6 次比较）。从树的形态看来，AVL 树不存在红黑树的“右倾”问题。也就是说，大量的顺序插入不会导致查询性能的降低，这从根本上解决了红黑树的问题。
  1598658808218.png

  • 优点：

    • 不错的查找性能（O（logn）），不存在极端的低效查找的情况。
    • 可以实现范围查找、数据排序。

  • mysql没有采用这个算法

    • 每一个树节点只存储了一个数据，一次磁盘 IO 只能取出来一个节点上的数据加载到内存里，那比如查询 id=7 这个数据我们就要进行磁盘 IO 三次，很消耗时间。设计数据库索引时需要首先考虑怎么尽可能减少磁盘 IO 的次数。磁盘 IO 有个有个特点，就是从磁盘读取 1B 数据和 1KB 数据所消耗的时间是基本一样的，根据这个思路，我们可以在一个树节点上尽可能多地存储数据，一次磁盘 IO 就多加载点数据到内存，这就是 B 树，B+树的设计原理了。

• B树

  • 一个节点可以存储多个键值，一个节点如果超过一定的键值就会分裂

  • 1598659014897.png

  • 例子： 一个存储了 16个数据的 B 树，查询 id=7 这个数据所要进行的磁盘 IO 为 2 次，相比于AVL 树而言磁盘 IO 次数降低为一半。

  • 优点：

    • 优秀检索速度，时间复杂度：B 树的查找性能等于 O（h*logn），其中 h 为树高，n 为每个节点关键词的个数；
    • 尽可能少的磁盘 IO，加快了检索速度；
    • 可以支持范围查找。

  • 在B树的前提下，引入了B+树

  • B 树和 B+树有什么不同呢？

    • B 树一个节点里存的是数据，而 B+树存储的是索引（地址），所以 B 树里一个节点存不了很多个数据，但是 B+树一个节点能存很多索引，B+树叶子节点存所有的数据。

    • B+树的叶子节点是数据阶段用了一个链表串联起来，便于范围查找。

    • 1598659052710.png

    • B+树节点存储的是索引，在单个节点存储容量有限的情况下，单节点也能存储大量索引，使得整个 B+树高度降低，减少了磁盘 IO。其次，B+树的叶子节点是真正数据存储的地方，叶子节点用了链表连接起来，这个链表本身就是有序的，在数据范围查找时，更具备效率。因此 Mysql 的索引用的就是 B+树，B+树在查找效率、范围查找中都有着非常不错的性能。

  • 数据结构最终选用B+树

    • hash很快，但每次IO只能取一个数
    • AVL和红黑树，在大量数据的情况下，IO操作太多
    • B树每个节点内存储的是数据，因此每个节点存储的分支太少
    • B+节点存储的是索引+指针(引用指向下一个节点)，可以存储大量索引，同时最终数据存储在叶子节点，并且有引用横向链接，可以在2-3次的IO操作内完成千万级别的表操作。

  Innodb 引擎和 Myisam 引擎的实现

  Mysql 底层数据引擎以插件形式设计，最常见的是 Innodb 引擎和 Myisam 引擎，用户可以根据个人需求选择不同的引擎作为 Mysql 数据表的底层引擎。我们刚分析了，B+树作为 Mysql 的索引的数据结构非常合适，但是数据和索引到底怎么组织起来也是需要一番设计，设计理念的不同也导致了 Innodb 和 Myisam 的出现，各自呈现独特的性能。

  MyISAM 虽然数据查找性能极佳，但是不支持事务处理。Innodb 最大的特色就是支持了 ACID 兼容的事务功能，而且他支持行级锁。Mysql 建立表的时候就可以指定引擎，

  区别：

  • 创建表后生成的文件不同
    • Innodb
      • frm:创建表的语句
      • idb:表里面的数据+索引文件
    • Myisam
      • frm:创建表的语句
      • MYD:表里面的数据文件（myisam data）
      • MYI:表里面的索引文件（myisam index）
  • 这两个引擎底层数据和索引的组织方式并不一样，MyISAM 引擎把数据和索引分开了，一人一个文件，这叫做非聚集索引方式；Innodb 引擎把数据和索引放在同一个文件里了，这叫做聚集索引方式。

  Myisam

  • 非聚集索引方式

    • MyISAM 用的是非聚集索引方式，即数据和索引落在不同的两个文件上。MyISAM 在建表时以主键作为 KEY 来建立主索引 B+树，树的叶子节点存的是对应数据的物理地址。我们拿到这个物理地址后，就可以到 MyISAM 数据文件中直接定位到具体的数据记录了。

    • 1598659357940.png

    • 当我们为某个字段添加索引时，我们同样会生成对应字段的索引树，该字段的索引树的叶子节点同样是记录了对应数据的物理地址，然后也是拿着这个物理地址去数据文件里定位到具体的数据记录。

  • 聚集索引方式

    • InnoDB 是聚集索引方式，因此数据和索引都存储在同一个文件里。首先 InnoDB 会根据主键 ID 作为 KEY 建立索引 B+树

    • 1598659404206.png

    • 建表的时候 InnoDB 就会自动建立好主键 ID 索引树，这也是为什么 Mysql 在建表时要求必须指定主键的原因

      • 在执行 select * from user_info where id=15 这个语句时，InnoDB 就会查询这颗主键 ID 索引 B+树，找到对应的 user_name='Bob'
      • 当我们为表里某个字段加索引时 InnoDB 会怎么建立索引树呢？比如我们要给 user_name 这个字段加索引，那么 InnoDB 就会建立 user_name 索引 B+树，节点里存的是 user_name 这个 KEY，叶子节点存储的数据的是主键 KEY
      • 拿到主键 KEY 后，InnoDB 才会去主键索引树里根据刚在 user_name 索引树找到的主键 KEY 查找到对应的数据。
      • 为什么 InnoDB 只在主键索引树的叶子节点存储了具体数据，但是其他索引树却不存具体数据呢，而要多此一举先找到主键，再在主键索引树找到对应的数据呢?
        • InnoDB 需要节省存储空间。一个表里可能有很多个索引，InnoDB 都会给每个加了索引的字段生成索引树，如果每个字段的索引树都存储了具体数据，那么这个表的索引数据文件就变得非常巨大。
  • MyISAM 查询性能更好，从上面索引文件数据文件的设计来看也可以看出原因：MyISAM 直接找到物理地址后就可以直接定位到数据记录，但是 InnoDB 查询到叶子节点后，还需要再查询一次主键索引树，才可以定位到具体数据。等于 MyISAM 一步就查到了数据，但是 InnoDB 要两步，那当然 MyISAM 查询性能更高。