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）平衡：到叶子节点的各个路径深度是符合平衡要求的。

可以看到B树数据和key存在一起，这样一个页面存储的索引信息就会极大减少，同时范围扫描要不断回到父节点，造成更多的磁盘io，B+树对于这两点进行了改进，其结构如下：

可以看到，B+树只有叶子节点存储数据，这样大大减小了查找数据时的磁盘io，可以看一个例子，假设一条记录为1k，一个叶子节点（一个页）可以存储16条记录，对于非叶子节点来说，以bigint为索引的话一个节点就占用8+6（在innodb中指针为6字节），这样一共就是14字节，一页可以存储16k/14=1170个非叶子节点，树为三层时就能存储1170*1170*16，也就是两千万左右的数据。

4.2 InnoDB聚簇和非聚簇索引查找原理和源码解析

聚簇索引的结构就和上一节图中一致，可以直接查找到数据；而非聚簇索引在叶子节点只记录主键值，获取数据的话再根据主键值进行查找。

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);
}