MySQL技術內幕:InnoDB索引技術
0.簡介
本文主要介紹MySQL InnoDB存儲引擎的索引技術,包含其支持的類型,語法,查看方式,優化方式以及對于其中B+ Tree索引的原理和代碼進行詳細的解讀。
1.MySQL索引類型介紹
1.1 數據結構分類
1)B+ Tree索引:其是基于B+樹數據結構實現,支持范圍查詢和排序操作。
CREATE INDEX index_name ON table_name (column_name);
2)哈希索引:使用hash table實現,支持等值的查詢。
CREATE INDEX index_name ON table_name (column_name) USING HASH;
3)全文索引:全文索引是通過倒排索引來實現,用以支持全文搜索。
CREATE FULLTEXT INDEX index_name ON table_name (column_name);
4)R-Tree索引:其基于R-Tree數據結構實現,支持空間數據查詢。
CREATE SPATIAL INDEX index_name ON table_name (column_name);
1.2 功能分類
1)主鍵索引:唯一標識表中每一行數據,不允許出現null值。
CREATE TABLE table_name (
id INT PRIMARY KEY,
...
);
2)唯一索引:確保索引列的值唯一,允許出現null值。
CREATE UNIQUE INDEX index_name ON table_name (column_name);
3)普通索引:最基本的索引類型,沒有任何約束。
CREATE INDEX index_name ON table_name (column_name);
4)組合索引:基于多個列創建的索引,其遵循最左前綴索引。
CREATE INDEX index_name ON table_name (column1, column2, ...);
1.3 存儲方式分類
1)聚簇索引:索引的葉子節點存儲完整的行數據,一個表只能有一個,就是主鍵索引。
2)非聚簇索引:索引的葉子節點存儲主鍵的值或者行指針,一個表能包含很多的非聚簇索引、非主鍵索引。
2.索引管理
2.1 查看索引
SHOW INDEX FROM table_name;
2.2 刪除索引
DROP INDEX index_name ON table_name;
2.3 修改索引
MySQL對于修改索引沒有支持,可以先刪除再創建。
DROP INDEX index_name ON table_name;
CREATE INDEX new_index_name ON table_name (column_name);
3.索引建立和設計原則
3.1 如何判斷是否需要索引
索引建立的判斷可以分兩步進行考慮:1.是否建立索引:主要考慮索引的資源占用,對插入和更新的影響以及備份恢復的影響;2.索引類型選擇:考慮創建索引以及使用查詢的速度,索引大小,索引支持的類型等。
3.2 設計原則
圖片
4. B+ Tree索引原理解讀
4.1 B+ Tree的產生
建立支持快速范圍查找和排序操作的索引其本質上就是建立一個有序的結構,通過使用它來縮小數據范圍,將隨機事件變為順序事件。那么對于實現來說如何快速縮小范圍,最容易想到的是分段和二分查找,但就分段來說,其無法確定分段范圍;而對于二分查找定位,常見的結構是二叉搜索樹,有了搜索方式,接下來就是考慮操作成本,對于數據庫系統來說,數據在磁盤存儲,所以需要考慮磁盤io,二叉搜索樹作為索引可能面臨多次io(不斷通過指針跳到不同頁面)。
有了上述操作成本問題,接下來就對于二叉搜索樹進行改良,第一個版本是B樹,其特點和結構如下,可以看到一個元素就是一個數據:
1)多路平衡:每個節點可以包含多個鍵(key)和子節點。
2)數據有序:節點之間是有序的。
3)平衡:到葉子節點的各個路徑深度是符合平衡要求的。
圖片
image.png
可以看到B樹數據和key存在一起,這樣一個頁面存儲的索引信息就會極大減少,同時范圍掃描要不斷回到父節點,造成更多的磁盤io,B+樹對于這兩點進行了改進,其結構如下:
圖片
圖片
可以看到,B+樹只有葉子節點存儲數據,這樣大大減小了查找數據時的磁盤io,可以看一個例子,假設一條記錄為1k,一個葉子節點(一個頁)可以存儲16條記錄,對于非葉子節點來說,以bigint為索引的話一個節點就占用8+6(在innodb中指針為6字節),這樣一共就是14字節,一頁可以存儲16k/14=1170個非葉子節點,樹為三層時就能存儲1170*1170*16,也就是兩千萬左右的數據。
4.2 InnoDB聚簇和非聚簇索引查找原理和源碼解析
聚簇索引的結構就和上一節圖中一致,可以直接查找到數據;而非聚簇索引在葉子節點只記錄主鍵值,獲取數據的話再根據主鍵值進行查找。
image.png
4.2.1 核心結構和流程
1)數據結構
//核心結構如下
/** Persistent cursor */
struct btr_pcur_t;
/** B-tree cursor */
struct btr_cur_t;
/** B-tree search information for the adaptive hash index */
struct btr_search_t;
2)插入:其核心流程包含兩步:1.查找插入位置;2.有空間就直接插入,沒有空間就分裂節點遞歸插入
/** Tries to perform an insert to a page in an index tree, next to cursor.
It is assumed that mtr holds an x-latch on the page. The operation does
not succeed if there is too little space on the page. If there is just
one record on the page, the insert will always succeed; this is to
prevent trying to split a page with just one record.
@return DB_SUCCESS, DB_WAIT_LOCK, DB_FAIL, or error number */
dberr_t btr_cur_optimistic_insert(
ulint flags, /*!< in: undo logging and locking flags: if not
zero, the parameters index and thr should be
specified */
btr_cur_t *cursor, /*!< in: cursor on page after which to insert;
cursor stays valid */
ulint **offsets, /*!< out: offsets on *rec */
mem_heap_t **heap, /*!< in/out: pointer to memory heap, or NULL */
dtuple_t *entry, /*!< in/out: entry to insert */
rec_t **rec, /*!< out: pointer to inserted record if
succeed */
big_rec_t **big_rec, /*!< out: big rec vector whose fields have to
be stored externally by the caller, or
NULL */
que_thr_t *thr, /*!< in: query thread or NULL */
mtr_t *mtr) /*!< in/out: mini-transaction;
if this function returns DB_SUCCESS on
a leaf page of a secondary index in a
compressed tablespace, the caller must
mtr_commit(mtr) before latching
any further pages */
3)查找:其從根節點逐層向下查找,最后返回匹配的游標。
/** Searches an index tree and positions a tree cursor on a given level.
NOTE: n_fields_cmp in tuple must be set so that it cannot be compared
to node pointer page number fields on the upper levels of the tree!
Note that if mode is PAGE_CUR_LE, which is used in inserts, then
cursor->up_match and cursor->low_match both will have sensible values.
If mode is PAGE_CUR_GE, then up_match will a have a sensible value.
If mode is PAGE_CUR_LE , cursor is left at the place where an insert of the
search tuple should be performed in the B-tree. InnoDB does an insert
immediately after the cursor. Thus, the cursor may end up on a user record,
or on a page infimum record. */
void btr_cur_search_to_nth_level(
dict_index_t *index, /*!< in: index */
ulint level, /*!< in: the tree level of search */
const dtuple_t *tuple, /*!< in: data tuple; NOTE: n_fields_cmp in
tuple must be set so that it cannot get
compared to the node ptr page number field! */
page_cur_mode_t mode, /*!< in: PAGE_CUR_L, ...;
Inserts should always be made using
PAGE_CUR_LE to search the position! */
ulint latch_mode, /*!< in: BTR_SEARCH_LEAF, ..., ORed with
at most one of BTR_INSERT, BTR_DELETE_MARK,
BTR_DELETE, or BTR_ESTIMATE;
cursor->left_block is used to store a pointer
to the left neighbor page, in the cases
BTR_SEARCH_PREV and BTR_MODIFY_PREV;
NOTE that if has_search_latch
is != 0, we maybe do not have a latch set
on the cursor page, we assume
the caller uses his search latch
to protect the record! */
btr_cur_t *cursor, /*!< in/out: tree cursor; the cursor page is
s- or x-latched, but see also above! */
ulint has_search_latch,
/*!< in: info on the latch mode the
caller currently has on search system:
RW_S_LATCH, or 0 */
const char *file, /*!< in: file name */
ulint line, /*!< in: line where called */
mtr_t *mtr) /*!< in: mtr */
4)刪除:其核心操作如下:查找刪除位置;如果刪除后節點仍然滿足最小鍵值數量要求,直接刪除(樂觀刪除),如果刪除后節點不滿足最小鍵值數量要求,合并節點并遞歸刪除(悲觀刪除)。
/** Removes the record on which the tree cursor is positioned on a leaf page.
It is assumed that the mtr has an x-latch on the page where the cursor is
positioned, but no latch on the whole tree.
@param[in] cursor cursor on leaf page, on the record to delete; cursor stays
valid: if deletion succeeds, on function exit it points to the successor of the
deleted record
@param[in] flags BTR_CREATE_FLAG or 0
@param[in] mtr if this function returns true on a leaf page of a secondary
index, the mtr must be committed before latching any further pages
@return true if success, i.e., the page did not become too empty */
inline bool btr_cur_optimistic_delete(btr_cur_t *cursor,
ulint flags [[maybe_unused]],
mtr_t *mtr) {
return btr_cur_optimistic_delete_func(cursor, IF_DEBUG(flags, ) mtr);
}