常見的索引類型：哈希表、有序數組、搜索樹。
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）無關了.