MySQL技術(shù)內(nèi)幕:InnoDB索引技術(shù)
0.簡介
本文主要介紹MySQL InnoDB存儲引擎的索引技術(shù),包含其支持的類型,語法,查看方式,優(yōu)化方式以及對于其中B+ Tree索引的原理和代碼進(jìn)行詳細(xì)的解讀。
1.MySQL索引類型介紹
1.1 數(shù)據(jù)結(jié)構(gòu)分類
1)B+ Tree索引:其是基于B+樹數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn),支持范圍查詢和排序操作。
CREATE INDEX index_name ON table_name (column_name);2)哈希索引:使用hash table實(shí)現(xiàn),支持等值的查詢。
CREATE INDEX index_name ON table_name (column_name) USING HASH;3)全文索引:全文索引是通過倒排索引來實(shí)現(xiàn),用以支持全文搜索。
CREATE FULLTEXT INDEX index_name ON table_name (column_name);4)R-Tree索引:其基于R-Tree數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn),支持空間數(shù)據(jù)查詢。
CREATE SPATIAL INDEX index_name ON table_name (column_name);1.2 功能分類
1)主鍵索引:唯一標(biāo)識表中每一行數(shù)據(jù),不允許出現(xiàn)null值。
CREATE TABLE table_name (
id INT PRIMARY KEY,
...
);2)唯一索引:確保索引列的值唯一,允許出現(xiàn)null值。
CREATE UNIQUE INDEX index_name ON table_name (column_name);3)普通索引:最基本的索引類型,沒有任何約束。
CREATE INDEX index_name ON table_name (column_name);4)組合索引:基于多個(gè)列創(chuàng)建的索引,其遵循最左前綴索引。
CREATE INDEX index_name ON table_name (column1, column2, ...);1.3 存儲方式分類
1)聚簇索引:索引的葉子節(jié)點(diǎn)存儲完整的行數(shù)據(jù),一個(gè)表只能有一個(gè),就是主鍵索引。
2)非聚簇索引:索引的葉子節(jié)點(diǎn)存儲主鍵的值或者行指針,一個(gè)表能包含很多的非聚簇索引、非主鍵索引。
2.索引管理
2.1 查看索引
SHOW INDEX FROM table_name;2.2 刪除索引
DROP INDEX index_name ON table_name;2.3 修改索引
MySQL對于修改索引沒有支持,可以先刪除再創(chuàng)建。
DROP INDEX index_name ON table_name;
CREATE INDEX new_index_name ON table_name (column_name);3.索引建立和設(shè)計(jì)原則
3.1 如何判斷是否需要索引
索引建立的判斷可以分兩步進(jìn)行考慮:1.是否建立索引:主要考慮索引的資源占用,對插入和更新的影響以及備份恢復(fù)的影響;2.索引類型選擇:考慮創(chuàng)建索引以及使用查詢的速度,索引大小,索引支持的類型等。
3.2 設(shè)計(jì)原則
圖片
4. B+ Tree索引原理解讀
4.1 B+ Tree的產(chǎn)生
建立支持快速范圍查找和排序操作的索引其本質(zhì)上就是建立一個(gè)有序的結(jié)構(gòu),通過使用它來縮小數(shù)據(jù)范圍,將隨機(jī)事件變?yōu)轫樞蚴录D敲磳τ趯?shí)現(xiàn)來說如何快速縮小范圍,最容易想到的是分段和二分查找,但就分段來說,其無法確定分段范圍;而對于二分查找定位,常見的結(jié)構(gòu)是二叉搜索樹,有了搜索方式,接下來就是考慮操作成本,對于數(shù)據(jù)庫系統(tǒng)來說,數(shù)據(jù)在磁盤存儲,所以需要考慮磁盤io,二叉搜索樹作為索引可能面臨多次io(不斷通過指針跳到不同頁面)。
有了上述操作成本問題,接下來就對于二叉搜索樹進(jìn)行改良,第一個(gè)版本是B樹,其特點(diǎn)和結(jié)構(gòu)如下,可以看到一個(gè)元素就是一個(gè)數(shù)據(jù):
1)多路平衡:每個(gè)節(jié)點(diǎn)可以包含多個(gè)鍵(key)和子節(jié)點(diǎn)。
2)數(shù)據(jù)有序:節(jié)點(diǎn)之間是有序的。
3)平衡:到葉子節(jié)點(diǎn)的各個(gè)路徑深度是符合平衡要求的。
圖片
image.png
可以看到B樹數(shù)據(jù)和key存在一起,這樣一個(gè)頁面存儲的索引信息就會極大減少,同時(shí)范圍掃描要不斷回到父節(jié)點(diǎn),造成更多的磁盤io,B+樹對于這兩點(diǎn)進(jìn)行了改進(jìn),其結(jié)構(gòu)如下:
圖片
圖片
可以看到,B+樹只有葉子節(jié)點(diǎn)存儲數(shù)據(jù),這樣大大減小了查找數(shù)據(jù)時(shí)的磁盤io,可以看一個(gè)例子,假設(shè)一條記錄為1k,一個(gè)葉子節(jié)點(diǎn)(一個(gè)頁)可以存儲16條記錄,對于非葉子節(jié)點(diǎn)來說,以bigint為索引的話一個(gè)節(jié)點(diǎn)就占用8+6(在innodb中指針為6字節(jié)),這樣一共就是14字節(jié),一頁可以存儲16k/14=1170個(gè)非葉子節(jié)點(diǎn),樹為三層時(shí)就能存儲1170*1170*16,也就是兩千萬左右的數(shù)據(jù)。
4.2 InnoDB聚簇和非聚簇索引查找原理和源碼解析
聚簇索引的結(jié)構(gòu)就和上一節(jié)圖中一致,可以直接查找到數(shù)據(jù);而非聚簇索引在葉子節(jié)點(diǎn)只記錄主鍵值,獲取數(shù)據(jù)的話再根據(jù)主鍵值進(jìn)行查找。
image.png
4.2.1 核心結(jié)構(gòu)和流程
1)數(shù)據(jù)結(jié)構(gòu)
//核心結(jié)構(gòu)如下
/** 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.有空間就直接插入,沒有空間就分裂節(jié)點(diǎn)遞歸插入
/** 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)查找:其從根節(jié)點(diǎn)逐層向下查找,最后返回匹配的游標(biāo)。
/** 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)刪除:其核心操作如下:查找刪除位置;如果刪除后節(jié)點(diǎn)仍然滿足最小鍵值數(shù)量要求,直接刪除(樂觀刪除),如果刪除后節(jié)點(diǎn)不滿足最小鍵值數(shù)量要求,合并節(jié)點(diǎn)并遞歸刪除(悲觀刪除)。
/** 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);
}





















