相信很多程式員朋友對資料的索引并不陌生，最常見的索引是 B+ Tree 索引，索引可以加快資料庫的檢索速度，但是會降低新增、修改、删除操作的速度，一些錯誤的寫法會導緻索引失效等等。
但是如果被問到，為什麼用了索引之後，查詢就會變快？B+ Tree 索引的原理是什麼？這時候很多人可能就不知道了，今天我就以 MySQL 的 InnoDB 引擎為例，講一講 B+ Tree 索引的原理。
索引的基礎知識
MySQL 的基本存儲結構是頁，大概就是這個樣子的：
- 當我們用 MySQL 的 InnoDB 引擎建立表，有且隻能有一個主鍵；如果我們沒有顯示地指定之間，那麼MySQL 會自動生成一個隐含字段作為主鍵；
- 聚集索引：以主鍵建立的索引；聚集索引的葉子節點存儲的是表中的資料；
- 非聚集索引：非主鍵建立的索引；非聚集索引在葉子節點存儲的是主鍵和索引列；使用非聚集索引查詢資料，會查詢到葉子上的主鍵，再根據主鍵查到資料（這個過程叫做回表）。
頁和頁之間、頁和資料之間的關系
我們以聚集索引做講解，頁和頁之間、以及頁和資料之間的關系是這樣的：
- 資料頁和資料頁之間，組成一個雙向連結清單；
- 每個資料頁中的記錄，是一個單向連結清單；
- 每個資料頁都根據内部的記錄生成一個頁目錄（Page directory），如果是主鍵的話，可以在頁目錄中使用二分法快速定位；
- 如果我們根據一個非主鍵、非索引列進行查詢，那麼需要周遊雙向連結清單，找到所在的頁；再周遊頁内的單向連結清單；如果表内資料很大的話，這樣的查詢就會很慢。
B+ Tree 索引的原理
先讓我們看看 B+ Tree 索引大概是什麼樣子（以聚集/主鍵索引為例）：
- 假如這時候我們要查詢 id = 16 的資料：
- 查詢頁-1，找到頁-2 存儲的是小于 30 的資料；
- 查詢頁-2，找到頁-5 存儲的是 10~20 的資料；
- 查詢頁-5，找到 id = 16 的資料。
很顯然，沒有用索引的時候，需要周遊雙向連結清單來定位對應的頁，而有了索引，則可以通過一層層“目錄”定位到對應的頁上。
為什麼 B+ Tree 索引會降低新增、修改、删除的速度
- B+ Tree 是一顆平衡樹，如果對這顆樹新增、修改、删除的話，會破壞它的原有結構；
- 我們在做資料新增、修改、删除的時候，需要花額外的時間去維護索引；
- 正因為這些額外的開銷，導緻索引會降低新增、修改、删除的速度。