常见的索引类型：哈希表、有序数组、搜索树。
mysql之普通索引和唯一索引。
执行查询的语句是 select id from T where k=5
这个查询语句在索引树上查找的过程，先是通过 B+ 树从树根开始，按层搜索到叶子节点，也就是图中右下角的这个数据页，然后可以认为数据页内部通过二分法来定位记录。
InnoDB的索引组织结构：
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 的处理流程如下：
第二种情况是，这个记录要更新的目标页不在内存中
这时，InnoDB 的处理流程如下：
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）。这条更新语句做了如下的操作（按照图中的数字顺序）：
带change buffer的更新过程：
select * from t where k in (k1, k2) ,如果读语句发生在更新语句后不久，内存中的数据都还在，那么此时的这两个读操作就与系统表空间（ibdata1）和 redo log（ib_log_fileX）无关了.