使用索引的初衷是为了快速的查询内容。
但是如果索引设置的过多，为了维护索引结构，会减慢写的速度；所以当前只对部分字段索引。
什么是好的索引？
即字段的取值范围很广，精确定位多个数值中的一个，这样才可以发挥索引的价值。
LSM-Tree
先看一个最基础的情况，存储使用追加式的顺序文件，索引使用Hash（key） 基于内存查找，值是数据在文件中的字节偏移量。
随着文件不断追加，可以定期将文件分段，定期压缩，定期合并。
将每一个分段都在内存中保存自己的哈希表。
如果不想每一次启动都重新建立hashmap，可以选择将hahsmap快照到磁盘，加快启动。
为了防止并发问题，这个简单场景值允许一个写线程。
但是这个模型，hahs的内存占用很大，同时hash的不确定性会造成大量的随机IO，也会存在区间查询慢的问题。
于是可以选择将hahmap修改为按照 key-value 排序字符串表。
这个时候就可以值存储稀疏索引，然后跳跃查找了。
这个结构引申为LSM-Tree
B 树
上述的LSM Tree 基于内存排序的索引模型还是过于简陋了；
现在主流的是磁盘中存储索引结构
这里构建了N叉树，一个节点的值按照key排序，可以高性能的范围查询。
树的节点存储单位为页，节点与节点之间的关联是页面的引用磁盘地址。至于一个页包含多少个子页引用，一般是几百个。
页中存储的是行记录数据。
但是为了节省页空间，让页存在足够空间存储子页的范围描述内容，以提高分支因子，降低层数 == 降低查找数量
选择页里面不存储指向数据的引用，而是存储缩略信息，树的叶子节点保存完整的记录引用。
这个树称之为 B+树。
B+树
B+树存储中，分为 index page 和 leaf page
index page 是辅助查找到 leaf page 的工具 ，全部的数据都是存储在叶子结点中 ， 并且叶子结点存储关联的指针的相互查找到。
如果主键索引在叶子结点中是顺序存储的，那么被称为索引组织表。
索引按照叶子结点的存储类型分为： 聚集索引( clustered index) 和 辅助索引 （secordary index）
- 聚集索引: 主键构建的叶子结构存储全部的行数据； 对于一次查找优先使用聚集索引。叶子结点是数据页。非叶子结点是索引页：由键值和指向数据页的偏移量组成 - 即叶子结点存储的是指向真实数据页的地址
- 辅助索引: 叶子结点为主键的id ，即存储的是非主键索引
-
注意 innodb中数据页的存储可能不是物理上连续的，而是使用逻辑上的相互引用完成的逻辑的顺序
关于 InnoDB 的表结构：
- 在 InnoDB 中，每一张表其实就是多个 B+ 树，即一个聚集索引树和多个辅助索引树。
- 执行查询的效率，使用主键索引 > 使用非主键索引 > 不使用索引。
- 如果不使用索引进行查询，则从主索引 B+ 树的叶子节点进行遍历
假设，我们有一个主键列为 ID 的表，表中有字段 k，并且在 k 上有索引
mysql> create table T(
id int primary key,
k int not null,
name varchar(16),
index (k))engine=InnoDB;表中 R1~R5 的 (ID,k) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，两棵树的示例示意图如下
- 主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）
- 非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）
基于主键索引和普通索引的查询有什么区别？
- 如果语句是 select * from T where ID=500，即主键查询方式，则只需要搜索 ID 这棵 B+ 树
- 如果语句是 select * from T where k=5，即普通索引查询方式，则需要先搜索 k 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表
索引长度过长会存在什么影响？
索引维护
B+ 树为了维护索引有序性，在插入新值的时候需要做必要的维护 。
可以想象一下，如果在叶子结点中插入一个新的值，需要判断一下左右的位置是不是满的，因为 index page 指向 的内容是 叶子节点的左右边界，如果满了，需要将左右边界的中间的位置的记录上移到 index page
而更糟的情况是，如果 R5 所在的数据页已经满了，根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能自然会受影响
当然有分裂就有合并。当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程
自增主键防止页分裂，逻辑删除并非物理删除防止页合并
重建索引 k:
MySQL 会创建一个新的索引结构，然后将原索引中的数据逐个插入到新索引中，最后删除原索引。这个过程可以去除冗余的节点，重新组织索引的物理结构，从而提高索引的性能。
alter table T drop index k;
alter table T add index(k);重建主键索引:
alter table T drop primary key;
alter table T add primary key(id);索引合并:
OPTIMIZE TABLE索引合并是将冗余的索引节点合并，从而优化索引的结构和性能。当索引被频繁更新、删除或者插入数据时，索引节点可能会变得不均衡，导致查询性能下降。通过索引合并，可以将冗余的节点合并为更少的节点，从而减少索引的高度，提高查询性能。
索引合并的原理是基于 B+ 树索引的结构。B+ 树是一种平衡的多叉树结构，节点中包含多个键值对，用于加速索引的查找和范围查询。当索引节点过多时，查询时需要进行更多的节点访问，从而导致查询性能下降。通过索引合并，可以将多个节点合并为一个更大的节点，从而减少节点数目，提高查询性能。
索引合理性评估 - cardinality
高选择性： 字段取值范围很大，查询命中少量行才可以发挥索引的价值
cardinality: 索引中不重复记录的数量， 理论上我们希望越大越好。
出于性能考虑 , 这个数值在 innodb 中是采样获取的预估值.
更新 cardinality 的时机： 超过 1/16数据发生变化的时候 、更新的行>200,000,000的时候
采样的算法: 采样 8个叶子节点 （p1+p2+…+p8）*A/8
联合索引 key(a,b)
联合索引属于辅助索引，叶子结点按照 (a,b) 顺序存储
如果固定a 查询b ， 可以得到 b 的顺序存储，但是从全局看 (a,b) b 是无序的
select * from t where a = 1 order by b; // 使用到了 (a,b) 索引覆盖索引
如果执行的语句是 select ID from T where k between 3 and 5，这时只需要查 ID 的值，而 ID 的值已经在 k 索引树上了，因此可以直接提供查询结果，不需要回表。也就是说，在这个查询里面，索引 k 已经“覆盖了”我们的查询需求，我们称为覆盖索引
由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段
假设市民表的定义是这样的：
CREATE TABLE `tuser` (
`id` int(11) NOT NULL,
`id_card` varchar(32) DEFAULT NULL,
`name` varchar(32) DEFAULT NULL,
`age` int(11) DEFAULT NULL,
`ismale` tinyint(1) DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `id_card` (`id_card`),
KEY `name_age` (`name`,`age`)
) ENGINE=InnoDB如果现在有一个高频请求，要根据市民的身份证号查询他的姓名，这个联合索引就有意义了
它可以在这个高频请求上用到覆盖索引，不再需要回表查整行记录，减少语句的执行时间
最左前缀原则
B+ 树这种索引结构，可以利用索引的“最左前缀”，来定位记录
索引项是按照索引定义里面出现的字段顺序排序的
如果你要查的是所有名字第一个字是“张”的人，你的 SQL 语句的条件是”where name like ‘张 %’“。这时，你也能够用上这个索引，查找到第一个符合条件的记录是 ID3，然后向后遍历，直到不满足条件为止
如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的
索引下推
以市民表的联合索引（name, age）为例。如果现在有一个需求：检索出表中“名字第一个字是张，而且年龄是 10 岁的所有男孩”。那么，SQL 语句是这么写的：
mysql> select * from tuser where name like '张%' and age=10 and ismale=1;前缀索引规则，所以这个语句在搜索索引树的时候，只能用 “张”，找到第一个满足条件的记录 ID3。当然，这还不错，总比全表扫描要好
然后呢？
在 MySQL 5.6 之前，只能从 ID3 开始一个个回表。到主键索引上找出数据行，再对比字段值
而 MySQL 5.6 引入的索引下推优化（index condition pushdown)， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数
InnoDB 在 (name,age) 索引内部就判断了 age 是否等于 10，对于不等于 10 的记录，直接判断并跳过。在我们的这个例子中，只需要对 ID4、ID5 这两条记录回表取数据判断，就只需要回表 2 次
MRR - Multi-Range Recod 优化
MRR可以讲随机的IO转换为顺序的IO
即在辅助索引那边的查询过程中，先缓存一下需要查询的数据，然后按照 row id 去排序，尽可能顺序查询到尽可能多的数据，然后再回表查询数据
ICP 优化
在执行辅助索引查找的时候，提前同时执行执行where条件过滤器，降低找数据的次数。
全文检索 - 倒排索引 invered index
当使用 like ‘%some%’ 查询的时候，就会使用到倒排索引
invered file index : 关键词 → 文档ID
full invered file index: 关键词 → 文档ID+文档的位置 — 这是 innodb 目前使用的
innodb 使用辅助表存储 file invered index ，也加了一个缓存来避免刷新辅助表过于的频繁
数据更新 → cache (32m) → 辅助表
如果遇到了异常关机，下一次会继续重新扫描文档完成辅助索引的创建
- 复习 数据库索引理论 (@2023-12-30)