本文主要是介绍MySQL技术内幕InnoDB存储引擎 学习笔记 第五章 索引与算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
如果索引太多，应用的性能会受到影响（每次插入都要更新索引并保存在磁盘上，增加了磁盘IO），如果索引太少，对查询性能又会产生影响，要找到一个平衡点。
InnoDB支持B+树索引和哈希索引。InnoDB的哈希索引是自适应的，InnoDB会根据表的使用情况为表生成哈希索引，不能人为干预是否在一张表中生成哈希索引。B+树构造类似二叉树，根据键值对快速找到数据，是目前关系型数据库系统中最常用、最有效的索引，B+树中的B不代表二叉，而是代表平衡，因为B+树是从最早的平衡二叉树演化而来，但B+树不是二叉树。
B+树索引并不能找到一个给定键值的具体行，而是查找数据行所在的页，然后MySQL把页读入内存，在内存中再查找。
平均来说，二分查找比顺序查找效率要高。每页中的Page Directory中的槽是按照主键顺序存放的，对于某一条具体记录的查询是通过对Page Directory进行二分查找得到的。
平衡二叉树定义：首先符合二叉查找树定义，其次必须满足任何节点的左右两个子树的高度最大差为1。
平衡二叉树对于查找的性能接近最高，要达到最好的性能，需要建立一颗最优二叉树，但最优二叉树的建立和维护需要大量操作，一般只需建立平衡二叉树。
平衡二叉树查询速度很快，但维护一颗平衡二叉树的代价很大，通常需要一次或多次左旋和右旋来得到插入或更新后树的平衡性，如下平衡二叉树：
当插入一个新值时，需要做以下操作保证平衡：
上图通过一次旋转（左旋）就使插入后的树重新变为平衡的了，有时需要多次旋转：
B+树中，所有记录节点都是按键值大小顺序存放在同一层的叶节点中，各叶节点使用指针进行连接，以下B+树高度为2，每页可存放4条记录，扇出为5：
二叉树的插入必须保证插入后叶节点中的记录依然有序：
对于图5-6中的B+树，如果插入28这个键值，发现Leaf Page和Index Page都没有满，直接插入即可：
在插入键值为70的行时，Leaf Page已经满了，但Index Page还没有满，如果插入到Leaf Page中，情况是50、55、60、65、70，根据中间的值60拆分叶节点：
上图中省略了叶节点间的指针。之后插入键值为95的行，此时Leaf Page和Index Page都满了，需要做两次拆分：
上表也省略了叶节点间的指针。可见不管怎么变化，B+树总会保持平衡，但为了保持平衡，对于新插入的键值可能需要做大量的拆分页操作，而B+树主要用于磁盘，页的拆分意味着磁盘操作，应在可能的情况下尽量减少页的拆分，因此提供了B+树旋转操作。
B+树旋转发生在Leaf Page已经满了，但其左右兄弟节点都没满的情况下，此时B+树不会先做拆分页的操作，而是将记录转移到所在页的兄弟节点上，通常优先检查左兄弟，因此图5-7插入键值70的行时，会做旋转操作，结果如下：
可见，采用旋转使B+树减少了一次页的拆分操作，且B+树的高度还是2。
B+树使用填充因子控制树的删除变化，50%是填充因子可设的最小值。B+树的删除操作也要保证删除后叶节点中的记录依然有序。
假设以下删除操作的填充因子是50%。
删除图5-9中B+树的键值为70的记录，直接删除即可：
之后删除键值为25的记录，该值还是Index Page中的值，删除该值后，将25的右兄弟节点更新到Index Page中：
之后删除键值为60的行，在删除后Leaf Page的填充因子小于50%，需要合并操作，同样，在删除Index Page中的相关记录后，需要做Index Page的合并操作，结果如下：
B+树索引本质是B+树在数据库中的实现，B+树索引在数据库中的一个特点是高扇出性，一般数据库中B+树的高度只有2~3层。
数据库中的B+树索引分为聚集索引和辅助聚集索引，其内部结构都是B+树，都是高度平衡的。
InnoDB引擎表是索引组织表，聚集索引是按每张表的主键构造一棵B+树，叶节点中存放着整张表的行记录，因此也让聚集索引的叶节点成为数据页，每个数据页通过一个双向链表进行链接。
实际的数据页只能按一棵B+树排序，因此每张表只能拥有一个聚集索引，查询优化器倾向于采用聚集索引，因为聚集索引能让我们在索引的叶节点上直接找到数据。
人为地使每个页内只能存放两个行记录：
CREATE TABLE t (a INT NOT NULL PRIMARY KEY,b VARCHAR(8000)
);
插入数据：
INSERT INTO t
SELECT 1, REPEAT('a', 7000);INSERT INTO t
SELECT 2, REPEAT('a', 7000);INSERT INTO t
SELECT 3, REPEAT('a', 7000);INSERT INTO t
SELECT 4, REPEAT('a', 7000);
构造的二叉树如下：
许多数据库文档说聚集索引按物理地址顺序存储数据，但如果聚集索引必须按特定顺序存放物理记录，维护成本会非常高，聚集索引并不是物理上的连续，而是逻辑上连续的。
由于聚集索引定义了数据的逻辑顺序，能很快地访问针对主键范围值的查询：
进行如上范围查询时，通过叶节点上层节点就可以得到页的范围，之后读数据页即可。上图的rows列给的是查询结果的预估返回行数，不是确切值。
辅助索引（非聚集索引）叶节点不包含行的全部数据，叶节包含键。
辅助索引不影响数据在聚集索引中的组织，每张表上可以有多个辅助索引。通过辅助索引寻找数据时，会先使用辅助索引找到辅助索引的叶子节点中的聚集索引的主键，再通过主键索引找到完整的行记录。
对于其他数据库，如SQLserver有一种不是索引组织的表，称为堆表，在数据的插入方面，与MySQL的MyISAM引擎相似。堆表上的索引都是非聚集的，且堆表没有主键，它的书签是一个行标识符，可用如“文件号：页号：槽号”的格式定位磁盘上实际的行。
堆表的非聚集索引不需要再通过主键对聚集索引进行查找，在只读的情况下，书签为行标识符方式的非聚集索引可能比书签为主键的非聚集索引快，但当表进行增删改等DML操作时，书签为行标识符方式的非聚集索引可能需要不断更新行标识符所指向数据页的位置，此时的开销就可能大于书签为主键方式的非聚集索引。对于排序和范围查找，索引组织表可通过B+树的中间节点就找到要查找的所有页，而堆表的特性使得这对其是不能实现的。但一般的数据库都通过预读技术避免多次的离散读操作，具体是堆表快还是索引组织表快，取决于具体情况，不存在哪个一定更优。
查看表上的索引：
SHOW INDEX FROM tableName;
给上表t添加一列c，并对该列创建非聚集索引：
ALTER TABLE t ADD c INT NOT NULL;update t set c = 0 - a;alter table t add key idx_c(c);
查看表t中a、c列的值：
select a, c from t;
运行它：
表t中会多出一个非聚集索引页，由于该表中只有4条数据，且列c只有4个字节，因此一个非聚集索引页即可存下，此时表t中非聚集索引和聚集索引关系如下：
可见辅助索引的叶子结点中只有列c的值和主键值，列c的值都是负数，以7fffffff方式进行内部存储，最高位0表示负值，实际值将其按位取反后加1，即-1。
当给已经有数据的表中添加一个非空列时，该列中数据自动变为0或空串。
用ALTER TABLE创建和删除索引语法：
ALTER TABLE tbl_name
| ADD {INDEX|KEY} [index_name]
[index_type] (index_col_name, ...) [index_option] ...;ALTER TABLE tbl_name
DROP PRIMARY KEY
| DROP {INDEX|KEY} index_name;
用CREATE/DROP INDEX创建和删除索引：
CREATE [UNIQUE] INDEX index_name
[index_type]
ON tbl_name (index_col_name, ...);DROP INDEX index_name ON tbl_name;
索引可以只对列上前100字节的数据索引，比如前面创建的表t，b列的类型为varchar(8000)：
ALTER TABLE t
ADD KEY idx_b(b(100));
MySQL的一个普遍问题是，添加或删除索引时，MySQL会先创建一张新临时表，然后把数据导入临时表，删除原表，再把临时表重命名为原来的表名，因此大表添加和删除索引时很慢。从InnoDB Plugin开始，支持一种称为快速索引创建的方法，它只限定于辅助索引，它对主键的创建和删除还是需要重建一张表，但对于辅助索引，InnoDB会先对表加一个S锁，创建索引过程中不用重建表，但在创建过程中只能对表进行读操作，这种方法删除辅助索引只需在InnoDB引擎的内部视图中将辅助索引的空间标记为可用，并删除MySQL内部视图中对于该表的索引定义即可。
联合索引指含多个列的索引。在表t上创建联合索引：
ALTER TABLE t
ADD KEY idx_a_b(a, c);
分析表上索引：
表上有四个索引：一个主键索引、一个列c上的索引、列b的前100个字节构成的索引、一个联合索引（占上表两行）。以上查询结果字段含义：
1.Table：索引所在表名。
2.Non_unique：是否是非唯一的索引，主键的该列是0，因为主键必须是唯一的。
3.Key_name：索引名，可用于DROP INDEX。
4.Seq_in_index：该列在索引中的位置，以联合索引idx_a_b为例，只有联合索引的该字段才会出现1以外的值。
5.Column_name：索引的列。
6.Collation：列以什么方式存在索引中。可以是’A’或NULL，B+树索引总是A，表示是排序的。如果使用了Heap引擎且建立的是Hash索引，会显示NULL，因为Hash根据Hash桶存放索引数据，而非对数据排序。
7.Cardinality：表示索引中唯一值的数目的估计。该值除表行数的结果应尽量接近1，如果太小要考虑是否要删除此索引。
8.Sub_part：是否只索引列的一部分，如索引idx_b，显示为100，表示只索引b列的前100个字节。索引整个列时该字段值为NULL。
9.Packed：关键字如何被压缩，NULL表示未压缩。
10.Null：索引列是否允许NULL值，允许时显示Yes，否则不显示。
11.Index_type：索引类型，InnoDB只支持B+树索引，因此上图中该字段值都是BTREE。
12.Comment：注释。
优化器会根据Cardinality值判断是否使用此索引，但这个值不是实时更新的，因为这样代价太大了，如要更新此值，使用以下命令：
ANALYZE TABLE t;
但此命令还存在一些问题，可能在每个系统上得到的结果不同。
在运行一段时间后，Cardinality可能会变为NULL，此时，可能会出现索引建立了但没有用到或explain两条一样的语句但最终结果不同（一个使用索引，一个全表扫描）的情况，此时最好做一次ANALYZE TABLE操作。
取值范围很广、几乎没有重复的字段（即高选择性）适合使用B+树索引。但如果访问字段是高选择性的，但取出的行数据占表中大部分数据时，MySQL不会使用B+树索引。
以下是一个例子，表member大约有500W条数据，usernick字段上有一个唯一索引，查找usernick为’David’的用户时，执行计划如下：
由于usernick字段具有高选择性，且以上查询选取表中很少行，所以使用了索引。但以下语句：
虽然条件列还是usernick，但优化器实际没有使用索引，这是因为它取出的行占表中很大部分：
查看以下以时间为范围搜索条件的SQL语句执行计划：
虽然只相差一天，但两条语句的执行计划却不同，第二条语句执行时，虽然可以使用idx_regdate索引，但优化器却没有使用该索引，而是使用全表扫描，优化器会通过EXPLAIN结果的rows字段预估查询可能得到的行，如果大于某值（作者猜测为20%表中数据），则B+树会选择全表扫描。但预估的返回行数的值是不准确的，这可能使优化器的选择出现问题。可强制使用索引：
SELECT id, userid, sex, registdate
INTO OUTFILE 'a'
FROM member
FORCE INDEX(idx_regdate)
WHERE registdate < '2006-04-24';
执行它：
如果不强制使用索引：
由此可见优化器的选择并不完全正确。
顺序读指顺序地读取磁盘上的块；随机读指访问的块不是连续的，需要磁盘的磁头不断移动。传统机械磁盘的瓶颈之一就是随机读取速度较低。
以下是在RAID的write back（cpu写内存时会同时修改内存和磁盘内容以保证两者一致）、write through（cpu写操作时只修改内存，磁盘修改会在内存数据要被新进入内存的数据取代时写入，RAID阵列一般自带电源，不用担心因停电等原因导致数据丢失）两种方式下通过sysbench测试的读取性能差异：
可见顺序读的性能较高。
B+树顺序读指按索引的叶节点链表顺序地读取所需的行数据，这只是逻辑上的顺序读，在物理磁盘上可能还是随机读取，但相对来说物理磁盘上的数据还是比较顺序的，因为区是64个连续的页。
随机读一般是访问辅助索引叶节点拿到主键后，再通过主键索引找数据，这一过程在磁盘上的访问是随机的。
当一次读取的表中内容过多时，对于非聚簇索引，随机读大量增加，对于聚簇索引，在磁盘上数据也不一定是顺序读取的，而随机读取性能远低于顺序读，因此才会出现选取大量数据时不使用索引而使用全表扫描的情况。
为提高读取性能，InnoDB引擎使用预读取技术，通过一次IO请求将多个页预读取到缓冲池中，InnoDB预测预读取的页马上会被访问。传统IO请求每次只读取一个页，在传统机械硬盘较低的IOPS（Input/Output Operations Per Second）下，预读可以大大提高读取性能。
InnoDB引擎的两个预读方法：
1.随机预读取：当一个区（64页）中13个页在缓冲区中，且在LRU列表前端（页是频繁被访问的），会将这个区中所有页都预读到内存。
2.线性预读取：如果一个区中24个页都被顺序访问了，则会预读取下一个区中所有页。
但MySQL的预读取却使得性能下降，InnoDB引擎官方从Plugin 1.0.4版本开始取消了随机预读取，线性预读取被保留了，并加入了innodb_read_ahead_threshold参数（默认值56），表示一个区中多少页被顺序访问时，InnoDB引擎才启用预读取读取下一个区中所有页。
固态硬盘内部构造与传统机械硬盘不同，它的随机读性能有质的飞跃，此时优化器的20%原理可能就不准确了。随着固态硬盘的普及，各数据库会加快这一方面的优化。
辅助索引的叶节点中包含主键，但不包含完整的行信息，InnoDB引擎总会先从辅助索引的叶节点判断是否能得到所需的数据，如以下例子：
CREATE TABLE t (a INT NOT NULL,b VARCHAR(20),PRIMARY KEY(a), key(b)
);INSERT INTO t
SELECT 1, 'kangaroo';INSERT INTO t
SELECT 2, 'dolphin';INSERT INTO t
SELECT 3, 'dragon';INSERT INTO t
SELECT 4, 'antelope';
如果此时执行SELECT * FROM t;，很多人以为输出如下：
但实际结果是：
上例中，辅助索引中包含了主键a的值，且使用的是b列上的辅助索引，因此不用主键就能得到所有列的数据，且通常辅助索引页中存放的数据条数比主键页上的要多，因此使用了辅助索引。解释这条SQL语句：
如果想得到对列a排序的结果，优化器会直接走主键，避免对a列的排序：
或可以强制使用主键：
SELECT *
FROM t
FORCE KEY(PRIMARY);
运行它：
联合索引本质上还是一棵B+树，但它的键值有一个以上。如有两个整型列(a,b)组成的联合索引，数据会按(a,b)的顺序在B+树中进行存放：
此时对于条件为WHERE a = xxx AND b = xxx的查询，可以使用以上索引。对于条件为WHERE a = xxx的查询也可以使用以上索引。但条件为WHERE b = xxx的查询不能使用以上索引，因为叶节点上b的值不是排序的。
使用联合索引时，可以对第二个键值进行排序，如我们查询某用户的购物情况，并按时间顺序排序，这时使用联合索引可以避免多一次排序操作，因为索引本身在叶节点已经排序了：
CREATE TABLE buy_log (userid INT UNSIGNED NOT NULL,buy_date DATE
);INSERT INTO buy_log
VALUES(1, '2009-01-01');INSERT INTO buy_log
VALUES(2, '2009-01-01');INSERT INTO buy_log
VALUES(3, '2009-01-01');INSERT INTO buy_log
VALUES(1, '2009-02-01');INSERT INTO buy_log
VALUES(3, '2009-02-01');INSERT INTO buy_log
VALUES(1, '2009-03-01');INSERT INTO buy_log
VALUES(1, '2009-04-01');ALTER TABLE buy_log
ADD KEY(userid);ALTER TABLE buy_log
ADD KEY(userid, buy_date);
如上，建立了两个包含userid字段的索引，如只对userid进行查询：
可见possible_keys字段显示有两个索引可以使用，但优化器选择的是userid，因为该叶节点包含单个键值，一个页中能包含的记录数更多。如果要取出userid为1的最近三次购买记录，并按购买日期排序：
以上语句也是两个索引可用，优化器选择了联合索引，因为这个联合索引中buy_date已经排序，如果强制使用userid单个索引：
可见会使用filesort（指排序，并不是字面意思在文件中完成排序）。执行上图语句前，先查看当前排序操作次数：
再执行语句：
再查看排序操作次数，发现增加了排序操作次数：
而如果使用联合索引会发现排序操作次数没有增加。
InnoDB引擎中自适应哈希索引使用的是散列表（哈希表）数据结构。将键通过哈希函数映射到哈希表中，发生碰撞时使用的一般是链接法，即将重复键值的数据放到一个链表中。
哈希函数最好避免碰撞的发生，数据库一般将关键字转换为自然数，然后采用除法散列的方法：h(k) = k mod m，即通过取k除以m的余数，将关键字k映射到m个槽中的某一个中。
InnoDB引擎的哈希索引冲突处理采用链表方式，哈希函数采用除法散列方式。将页转换为自然数时，先将表空间号左移20位，再加上该页在表空间中的偏移量即可，此数值就可以通过除法散列到哈希表的槽中。
自适应哈希索引是数据库自己创建并使用的，DBA不能对其进行干预。在配置文件中启用了参数innodb_adaptive_hash_index后，数据库启动时会自动创建槽数为innodb_buffer_pool_size/256的哈希表，如此参数值为10M，则启动时InnoDB会创建一个有10M/256=40960个槽的自适应哈希表。
自适应哈希索引对于字典类型查找非常快速，但对于范围查找就无能为力了。
查看当前自适应哈希索引使用情况：
SHOW ENGINE innodb STATUS;
运行它：
可以看到自适应哈希索引的大小、使用情况、每秒使用自适应哈希索引搜索和每秒不使用自适应哈希索引搜索的情况。
自适应哈希索引默认为开启。
这篇关于MySQL技术内幕InnoDB存储引擎 学习笔记 第五章 索引与算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
