关于索引数据模型

索引常见的三大数据模型

1. 哈希表
   1. 哈希表是常见的键值对(key->value)数据结构。有一个存放value的数组，key用哈希函数换算成一个确定的位置，将value放在数组的这个位置。
   2. 不可避免地，多个key值经过哈希函数的换算，会出现同一个值的情况。处理这种情况的一种方法是，拉出一个链表。在出现多个value的key哈希之后相同时，会生成一个链表存放value，好处是新增速度快，只需要往链表后面追加，缺点是区间查询的速度非常慢，需要全盘扫描。
2. 有序数组
   1. 有序数组在等值查询和区间查询场景中是非常有优秀的，犹豫存放的数值是有序的，使用二分法可以很快的锁定位置。区间查询时可以通过二分法找到最小值，然后从最小值开始遍历后面的值直到找到最大值。
   2. 从上面的查询来看有序数组是优点是非常明显的，但同样，缺点也非常明显。在中间插入值时，为了保证有序性，就需要挪动后面所有值，系统开销太大了。所以，有序数组适用于静态存储引擎，即数据不会修改的数据，如：2022年某个城市的所有人口信息，这类不会再修改的数据
3. 搜索树
   搜索树常见的有二叉树、N叉树
   1. 二叉树
      二叉树特点：一个父节点只能有两个子节点，左子节点的值小于父节点，右子节点的值大于父节点。优点：查询效率高。缺点：为了平衡二叉树，每次插入值时，开销较大，如果树的高度过大，如高度为20，就需要从20次io，如此，查询时间会变得特别长。
   2. N叉树
      N叉树特别：一个父节点可以有多个子节点，子节点的值从左到右依次递增。优点：相对于二叉树，N叉树的io次数相对少很多。MySQL默认N叉树，N叉树又可分为红黑树、B树等。

InnoDB索引模型

1. InnoDB索引默认B+树，每一个索引在InnoDB里面对应一颗B+树。
2. 索引类型分为主键索引和非主键索引
   1. 主键索引
      主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。
   2. 非主键索引
      非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。
   3. 主键索引和普通索引的查询区别
      如果语句是 select from T where ID=500，即主键查询方式，则只需要搜索 ID 这棵 B+ 树；
      如果语句是 select from T where k=5，即普通索引查询方式，则需要先搜索 k 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。