InnoDB索引最通俗的解释

浅浅的花香味﹌ 2022-05-25 01:47 185阅读 0赞

# 什么是索引 #

**索引是一种特殊的文件(`InnoDB`数据表上的索引是表空间的一个组成部分)内部数据结构使用的B+树，B树节点内部包含着对数据表里所有记录的引用指针**。更通俗的说，数据库索引好比是一本书前面的目录，能加快数据库的查询速度。上述SQL语句，在没有索引的情况下，数据库会遍历全部数据后选择符合条件的；而有了相应的索引之后，数据库会直接先在索引中查找符合条件的选项。如果我们把SQL语句换成“SELECT \* FROM article WHERE id=2000000”，那么你是希望数据库按照顺序读取完200万行数据以后给你结果还是直接在索引中定位呢？（注：一般数据库默认都会为主键生成索引）。

# 树 #

二叉查找树（Binary Search Tree），平衡二叉查找树（Balanced Binary Search Tree），红黑树(Red-Black Tree )，B-tree和B+-tree。前三者是典型的二叉查找树结构，其查找的时间复杂度O(log2N)与树的深度相关，那么降低树的深度自然会提高查找效率。

**二叉查找树**：左子树键值总是小于根的键值，右子树键值总是大于根的键值。因此中序遍历可以得到键值的排序输出。  
![这里写图片描述][70]  
上述中序输出就是：2 3 5 6 7 8。  
但是二叉查找树可以以任意的顺序插入，例如当数据2 3 5 6 7 8以有序的顺序插入时候，树的结构就是下图：  
![这里写图片描述][70 1]  
可以看到树已经出现了极度不平衡，查找速度一定和线性查找一样了。为了解决上述问题，出现了后续的树种。

**平衡二叉树**：为了提高二叉树的搜索的效率,减少树的平均搜索长度，提出了AVL树，**它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1（也就是高度的平衡），**且它的左子树和右子树都是一颗平衡二叉树。**为了维持高度的平衡，则频繁的插入和删除，会引起频繁的reblance（旋转以维持平衡），导致效率可能会下降。**具体代码如何编写，暂不考虑，因为每什么用。

**红黑树**：红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，**红黑树牺牲了绝对平衡，换取了少旋转。红黑树确保没有一条路径会比其他路径长出俩倍，且对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点，因而是接近平衡的。**  
红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。很好的解决了平衡二叉树旋转次数出现很多的可能。

红黑树具有5个性质：

*  每个结点要么是红的要么是黑的。
 *  根结点是黑的。
 *  每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
 *  如果一个结点是红的，那么它的两个儿子都是黑的。
 *  对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

正是红黑树的这5条性质，使一棵n个结点的红黑树始终保持了logn的高度，从而也就解释了上面所说的“红黑树的查找、**插入、删除的时间复杂度最坏为O(log n)**。具体如何插入、查找、删除，就根本不需要考虑了，实现起来相当的复杂。

**B树**：B树又叫做多叉平衡查找树。前面的平衡二叉树分支最多有2个，但是这里的B树分支可以有n个。分支多的好处就会形成一个矮胖矮胖的平衡二叉树。每个节点里面含有许多个键-值对。这就是B树。 **B树中的每个结点根据实际情况可以包含大量的关键字信息和分支(当然是不能超过磁盘块的大小，根据磁盘驱动(disk drives)的不同，一般块的大小在1k~4k左右)；这样树的深度降低了，这就意味着查找一个元素只要很少结点从外存磁盘中读入内存，很快访问到要查找的数据**。  
![这里写图片描述][70 2]  
上述就是一个B树。  
外部存储不同于内存的主要特性就是需要花费很多的时间去定位特定的页，但是页读取数据非常快。所以需要使用最少的时间来定位到相应的页。

对于在外存储器-磁盘上面的数据使用这种树，可以最大程度的减少IO操作。

**B+树**：是B树的变体。B+-tree的内部结点并没有指向关键字具体信息的指针，只有在叶子节点才会有每个关键字具体信息，且每个节点内部含有键值的冗余。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。  
![这里写图片描述][70 3]  
如上是一颗B+树，除了叶子节点之外节点内部仅仅含有键而已。到了最后叶子节点里面才含有每个键对应的值（指针指向关键信息）信息。

B+树特点：

*  所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
 *  所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

B+树的优点：

*  单一节点存储更多的元素（因为不含有对应的值，仅仅含有键），使得查询的IO次数更少。
 *  所有查询都要从根节点查找到叶子节点，查询性能稳定，相对于B树更加稳定，以为B+树只有叶子节点存储了对应的值信息。
 *  所有叶子节点形成有序双向链表，对于SQL的范围查询以及排序查询都很方便。
 *  B/B+树的共同优点的每个节点有更多的孩子，插入不需要改变树的高度，从而减少重新平衡的次数，非常适合做数据库索引这种需要持久化在磁盘，同时需要大量查询和插入的应用。树中节点存储这指向页的信息，可以快速定位到磁盘对应的页上面。

# InnoDB索引实现 #

B+树索引并不能找到一个给定键值的具体行。B+树索引能找到的只是被查找数据行所在的页。然后数据库通过把页读入到内存，再在内存中进行查找，最后得到要在找的数据。因为页目录中的槽是按照主键顺序排列的，所以在每一个页目录中，通过二分查找，定位到数据行所在的页，然后将整个页读入内存，进而将整个页中的单向链表遍历得到相应的行数据。下面几个链接中文章仔仔细细的详述了这中思维。

[InnoDB记录存储结构][InnoDB]

[InnoDB数据页结构][InnoDB 1]

[MySQL的索引实现][MySQL]

总结  
1、对于InnoDB存储引擎来说，在单个页中查找某条记录分为两种情况：

*  以主键为搜索条件，可以使用Page Directory通过二分法快速定位相应的用户记录。
 *  以其他列为搜索条件，需要按照记录组成的单链表依次遍历各条记录。

2、没有索引的情况下，不论是以主键还是其他列作为搜索条件，只能沿着页的双链表从左到右依次遍历各个页。

3、InnoDB存储引擎的索引是一棵B+树，完整的用户记录都存储在B+树第0层的叶子节点，其他层次的节点都属于内节点，内节点里存储的是目录项记录。InnoDB的索引分为两大种：

*  聚簇索引：以主键值的大小为页和记录的排序规则，在叶子节点处存储的记录包含了表中所有的列。
 *  二级索引或叫做辅助索引：以自定义的列的大小为页和记录的排序规则，在叶子节点处存储的记录内容是列内容 + 主键。二级节点查找需要查找二级节点B+树，然后再查看聚集索引B+树中叶子节点对应的记录内容。

4、MyISAM存储引擎的数据和索引分开存储，这种存储引擎的索引全部都是二级索引，在叶子节点处存储的是列 + 页号。

# InnoDB使用索引 #

1、在创建表的时候通过key或index指定索引。  
2、通过alter修改表的结构，添加索引。  
前面链接中已经说明了应该如何使用了。

# InnoDB索引失效 #

1、如果条件中有or，即使其中有部分条件带索引也不会使用，除非条件中的列全部有索引。  
![这里写图片描述][70 4]

2、like查询是以%开头  
![这里写图片描述][70 5]

3、如果列类型是字符串，那一定要在条件中将数据使用引号引用起来,否则不使用索引。  
![这里写图片描述][70 6]

4、如果mysql估计使用全表扫描要比使用索引快,则不使用索引。  
此外，查看索引的使用情况  
show status like ‘Handler\_read%’;  
大家可以注意：  
handler\_read\_key:这个值越高越好，越高表示使用索引查询到的次数  
handler\_read\_rnd\_next:这个值越高，说明查询低效

# InnoDB全文搜索 #

B+树索引的特点是支持前缀进行查找，例如`SELECT * FROM blog WHERE content like 'xxx%'`。对于`SELECT * FROM blog WHERE content like '%xxx'`，并不支持，这种模式会导致InnoDB扫描整个表，速度会非常慢。那么现在就需要一种方案解决这个问题。那就是全文索引。InnoDB 1.2版本开始，已经全面支持了全文索引(Full-Text Search )。**全文检索是将存储于数据库中的整本书或整篇文章中的任意内容单词查找出来的技术。**它可以根据需要获得全文中有关章、节、段、句、词等信息，也可以进行各种统计和分析。**全文索引使用倒排索引实现，辅助表中存储了单词与单词自身在一个或多个文档中的映射。**将整个表中单词所在的行及其位置全部索引出来。这样在需要从中检索出行中释放含有某个单词就很快了。  
表现形式就是｛单词，（单词所在文档ID ， 在具体文档中的位置）｝。  
![这里写图片描述][70 7]

1、使用全文索引  
为了进行全文本搜索，必须索引被搜索的列，而且要随着数据的改变不断地重新索引。在对表列进行适当设计后， MySQL会自动进行所有  
的索引和重新索引。

CREATE TABLE productnotes
    (
      note_id    int           NOT NULL AUTO_INCREMENT,
      prod_id    char(10)      NOT NULL,
      note_date datetime       NOT NULL,
      note_text  text          NULL ,
      PRIMARY KEY(note_id),
      FULLTEXT(note_text)
    ) ENGINE=InnoDB;
    //使用InnoDB引擎，并且通过FULLTEXT(note_text)指示对其进行索引，索引是单个列，
    //定义之后MySQL自动维护该索引，在增加、删除、更新行时候，索引自动更新。
    
    mysql> explain select note_text from productnotes where match(note_text) against('rabbit')\G;
    *************************** 1. row ***************************
               id: 1
      select_type: SIMPLE
            table: fulltxt
       partitions: NULL
             type: fulltext
    possible_keys: note_text
              key: note_text
          key_len: 0
              ref: const
             rows: 1
         filtered: 100.00
            Extra: Using where; Ft_hints: sorted
    1 row in set, 1 warning (0.01 sec)
    //提示使用了全文索引，加快索引起来。
    
    select note_id , note_text from fulltxt where match(note_text) against('rabbit')\G;
    *************************** 1. row ***************************
      note_id: 104
    note_text: Quantity varies, sold by the sack load.
    All guaranteed to be bright and orange, and suitable for use as rabbit bait.
    *************************** 2. row ***************************
      note_id: 110
    note_text: Customer complaint: rabbit has been able to detect trap, food apparently less effective now.
    2 rows in set (0.00 sec)
    //在索引之后，使用两个函数Match()和Against()执行全文本搜索
    //match指定搜索的列，against指定使用搜索的表达式。
    //传递给match的值，必须和FULLTEXT中定义的相同，包括次序，并且全文搜索不区分大小写。
    
    select note_id , note_text from fulltxt where note_text like '%rabbit%'\G;
    *************************** 1. row ***************************
      note_id: 104
    note_text: Quantity varies, sold by the sack load.
    All guaranteed to be bright and orange, and suitable for use as rabbit bait.
    *************************** 2. row ***************************
      note_id: 110
    note_text: Customer complaint: rabbit has been able to detect trap, food apparently less effective now.
    2 rows in set (0.00 sec)
    //等效于like,返回次序不同。而全文搜索返回的文本排序了。

2、演示全文索引的优先级  
等级由MySQL根据行中词的数目、唯一词的数目、整个索引中词的总数以及包含该词的行的数目计算出来。  
不包含词rabbit的行等级为0（因此不被前一例子中的WHERE子句选择）。确实包含词rabbit  
的两个行每行都有一个等级值，文本中词靠前的行的等级值比词靠后的行的等级值高。  
全文本搜索排除那些等级为0的行，然后按等级以降序排序。

3、使用查询扩展  
查询扩展用来设法放宽所返回的全文本搜索结果的范围。  
例如：你想找出所有提到anvils的注释。只有一个注释包含词anvils，但你还想找出可能与你的搜索有关的所有其他行，即使他们不包含anvils。  
方法：使用查询扩展时，MySQL对数据和索引进行两遍扫描来完成搜索。  
首先，进行一个基本的全文本搜索，找出与搜索条件匹配的所有行。  
其次， MySQL检查这些匹配行并选择所有有用的词。  
再其次， MySQL再次进行全文本搜索，这次不仅使用原来的条件，而且还使用所有有用的词。

select note_text from productnotes where match(note_text) against('anvils');
    //不使用查询扩展
    
    select note_text from productnotes where match(note_text) against('anvils' with query expansion);
    //使用查询扩展

# 参考 #

[参考1-小青蛙][InnoDB]  
[参看2-小青蛙][MySQL]  
参考3-InnoDB技术内幕详解

[70]: /images/20220525/dd4bf7d4de884217a1074e817d15d8c0.png
[70 1]: /images/20220525/1b9ec5965d4949f486f43f2b37d151a2.png
[70 2]: /images/20220525/19de5bbb990c4bf68593084cfabc8c31.png
[70 3]: /images/20220525/d19abd7bac0c4a39b70ecd4b867e07fa.png
[InnoDB]: https://mp.weixin.qq.com/s?__biz=MzIxNTQ3NDMzMw==&mid=2247483670&idx=1&sn=751d84d0ce50d64934d636014abe2023&chksm=979688e4a0e101f2a51d1f06ec75e25c56f8936321ae43badc2fe9fc1257b4dc1c24223699de&scene=21#wechat_redirect
[InnoDB 1]: https://mp.weixin.qq.com/s?__biz=MzIxNTQ3NDMzMw==&mid=2247483678&idx=1&sn=913780d42e7a81fd3f9b747da4fba8ec&chksm=979688eca0e101fa0913c3d2e6107dfa3a6c151a075c8d68ab3f44c7c364d9510f9e1179d94d&scene=21#wechat_redirect
[MySQL]: https://mp.weixin.qq.com/s?__biz=MzIxNTQ3NDMzMw==&mid=2247483701&idx=1&sn=bd229dd584f51ef4fe545d44ad8cdbf9&chksm=979688c7a0e101d1b5c752094013b78f5bd50ab905257ba82149d85d35ea07aba1a15b0e52b4#rd
[70 4]: /images/20220525/bcf7f8b44dae4ba2b258c94330e2d701.png
[70 5]: /images/20220525/b0c9af1359e0499b85b468d93871daaa.png
[70 6]: /images/20220525/b5c79abbb8a54532857bc0fa8e9566ce.png
[70 7]: /images/20220525/35f2771914b642e5bfd8bf4b680e97bf.png