1、索引常用的索引模型

常见的索引类型：哈希表、有序数组、搜索树。

• 哈希表：一种以键值对（key-value）存储数据的结构，我们只要输入待查找的键即key,就可以找到其对应的值value。哈希表这种结构适用于只有等值查询的场景。
• 有序数组：通过二分法进行查询，有序数组只适用于静态存储引擎。
• 二叉搜索树：父节点左子树所有节点的值小于父节点的值，右子树所有结点的值大于父节点的值。

2、查询过程

mysql之普通索引和唯一索引。
执行查询的语句是 select id from T where k=5
这个查询语句在索引树上查找的过程，先是通过 B+ 树从树根开始，按层搜索到叶子节点，也就是图中右下角的这个数据页，然后可以认为数据页内部通过二分法来定位记录。

• 对于普通索引来说，查找到满足条件的第一个记录 (5,500) 后，需要查找下一个记录，直到碰到第一个不满足 k=5 条件的记录。
• 对于唯一索引来说，由于索引定义了唯一性，查找到第一个满足条件的记录后，就会停止继续检索。

InnoDB的索引组织结构：

• InnoDB的数据按数据页为单位来读写的，当需要读一条记录的时候，以页为单位，将其整体读入内存，在InnoDB中，每个数据页的大小默认是16Kb。

• InnoDB是按页读写的，当找到k=5的记录的时候，所在的数据页就都在内存里。

  
  image.png

3、更新过程

change buffer:持久化的数据。InnoDB将更新操作缓存在 change buffer中,也就是说,change buffer 在内存中有拷贝，也会被写入到磁盘，主要节省的则是随机读磁盘的IO消耗。
change buffer 只限于用在普通索引的场景下，而不适用于唯一索引.

merge:将 change buffer 中的操作应用到原数据页，得到最新结果的过程。
merge执行流程：
1、从磁盘读入数据页到内存
2、从change buffer里找出这个数据页的change buffer记录，依次应用，得到新版数据页
3、写redo log,这个redo log包含了数据的变更和change buffer的变更。

change buffer 用的是 buffer pool 里的内存，因此不能无限增大。change buffer 的大小，可以通过参数 innodb_change_buffer_max_size=50 表示 change buffer 的大小最多只能占用 buffer pool 的 50%。

如果要在这张表中插入一个新记录 (4,400) 的话，InnoDB 的处理流程是怎样的。

第一种情况是，这个记录要更新的目标页在内存中
这时，InnoDB 的处理流程如下：

• 对于唯一索引来说，找到 3 和 5 之间的位置，判断到没有冲突，插入这个值，语句执行结束；
• 对于普通索引来说，找到 3 和 5 之间的位置，插入这个值，语句执行结束。

第二种情况是，这个记录要更新的目标页不在内存中
这时，InnoDB 的处理流程如下：

• 对于唯一索引来说，需要将数据页读入内存，判断到没有冲突，插入这个值，语句执行结束；
• 对于普通索引来说，则是将更新记录在 change buffer，语句执行就结束了。

4、change buffer和redo log

mysql> insert into t(id,k) values(id1,k1),(id2,k2);当前 k 索引树的状态，查找到位置后，k1 所在的数据页在内存 (InnoDB buffer pool) 中，k2 所在的数据页不在内存中。
分析这条更新语句，你会发现它涉及了四个部分：内存、redo log（ib_log_fileX）、 数据表空间（t.ibd）、系统表空间（ibdata1）。这条更新语句做了如下的操作（按照图中的数字顺序）：

• 1、Page 1 在内存中，直接更新内存；
• 2、Page 2 没有在内存中，就在内存的 change buffer 区域，记录下“我要往 Page 2 插入一行”这个信息
• 3、将上述两个动作记入 redo log 中（图中 3 和 4）。

带change buffer的更新过程：

image.png

select * from t where k in (k1, k2),如果读语句发生在更新语句后不久，内存中的数据都还在，那么此时的这两个读操作就与系统表空间（ibdata1）和 redo log（ib_log_fileX）无关了.

• 1、读 Page 1 的时候，直接从内存返回。
• 2、要读 Page 2 的时候，需要把 Page 2 从磁盘读入内存中，然后应用 change buffer 里面的操作日志，生成一个正确的版本并返回结果。

image.png