MySql-索引

这里有一点个人看法，我们理解数据库数据结构选型的时候，结合现实开发当中的情形，通常读占有大部分的情况，伴有数据新增，数据更新，数据删除的场景，那么一个数据库数据结构首先要满足我们对于查询速度的考量，其次插入数据，更新数据，删除数据也要有不俗的变现

• 索引的出现是为了提高查询效率

索引模型

• 提高读写效率的数据结构有很多，有三种最常见的数据结构
• 分别是：
  • 哈希表
  • 有序数组
  • 搜索树

哈希表

• 哈希表是一种以键-值(key-value)存储数据的结构。哈希表是通过计算key的哈希值将key换算成一个确定的位置，中间会有多个key计算hash相同的情况，value设置成一个链表，将值value追加到链表后边。
• 获取值的时候，通过传入的key获取对应的value链表，然后遍历链表，找到匹配的值
• 缺点：值value链表不是有序的，根据key获取到对应的链表结构时，需要遍历链表，找到对应的值。做区间查询的时候，必须全部扫描一遍。例如：查询【3，8】范围的内的所有数据。
• 适用场景：适合等值查询的场景

有序数组

• 适用场景：适合等值查询和范围查询场景，查询效率很高，有序数组索引只适用于静态存储引擎
• 缺点：不适合经常更新数据的场景，动态数组当中更新一次数组，后挪动后边的所有数据，变动太大，成本太高

搜索树

• 例如：二叉搜索树
  • 特点：左子节点小于父节点，右子节点大于父节点
  • 时间复杂度：O(log(N))
    • 为了保持搜索复杂度是O(log(N))，需要保证二叉搜索树是一个平衡二叉搜索树，这样每次更新的时间复杂度是O(log(N))
  • 索引选型：
    • 二叉树搜索效率最高，大多数数据库存储并不使用二叉树，而使用多叉树
    • 原因：索引不仅存储在内存当中，还要存储到磁盘上。为了让查询尽量减少读磁盘的操作，就必须让查询过程访问尽量少的数据库
    • 示例：例如有一颗一百万节点的平衡二叉树，树高20，一次查询可能需要访问20个数据块，在机械硬盘时代，从磁盘随机读一个数据块需要10ms左右的寻址时间，那么一个一百万行的表，如果使用二叉树来存储的话，单独访问一个行可能需要20个10ms的时间。

image-20231022183318951

InnoDB索引模型

• 表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表，都是存储在B+树当中
• 每一个索引在InnoDb里边对应一颗B+树

索引类型

• 主键索引和非主键索引
• 主键索引
  • 叶子节点存储的是整行数据，在InnoDB当中主键索引也被称为聚簇索引
• 非主键索引
  • 叶子节点存储的是主键的值，在InnoDB当中非主键索引也被称为二级索引

回表

• 主键查询方式，只需要搜索id这颗B+树
• 普通索引方式，需要先搜索普通索引树，得到主键的值，再到主键索引树搜索一次，这个过程称为回表
• 也就是说，基于非主键索引的查询需要多扫描一颗索引树，因此，在应用中应该多尽量使用主键查询