MySQL_02_InnoDB存储引擎默认使用B+树索引_innodb使用的是b树还是b+树

一、前言

人们谈论索引的时候,如果没有特别指明类型,那多半说的是B+Tree索引（MySQL默认存储引擎是InnoDB存储引擎，InnoDB存储引擎使用的是B+树索引）,它使用Tree数据结构来存储数据。

尽管大多数MySQL引擎都支持B+树索引，即使是使用B+树索引，不同存储引擎的实现方式也有所不同：
（1）MyISAM 使用前缀压缩技术使得索引更小,但 InnoDB则按照原数据格式进行存储；
（2）MyISAM 索引通过数据的物理位置引用被索引的行,而 InnoDB则根据主键引用被索引的行。

注意：只有B树和B+树，没有B-树。

二、从B树到B+树

2.1 B树

B树(B tree)是一种平衡的多路查找树,主要面向动态查找,通常用在文件系统中。

2.1.1 B树性质

一棵m阶的B树两种情况，要么为空树,要么为满足下列特性的m叉树：

(1)叶子节点：所有的叶子结点都出现在同一层,并且不带信息。叶子结点的双亲称为终端结点;

(2)每个节点：每个结点至多有m棵子树;（金手指：m叉树）

(3)根节点：若根结点不是终端结点,则至少有两棵子树;

(4)非根节点：除根结点之外的所有非终端结点至少有⌈m/2⌉棵子树;

(5)非终端节点(非叶子节点)：所有的非终端结点都包含以下数据: (n,A0,K1,A1,K2,…,Kn,An)

其中,n(⌈m/2⌉-1≤n≤m-1)为关键码的个数,Ki(1≤i≤n)为关键码,且Ki<K(i+1)(1≤i≤n-1),Ai(0≤i≤n)为指向子树根结点的指针,且指针Ai所指子树中所有结点的关键码均小于K(i+1)大于Ki。

一般情况下,B树的叶子结点可以看做是外部结点(即查找失败)的结点,通常称为外结点。实际上这些结点不存在,指向这些结点的指针为空。所以,B树的叶子可以不画出来。因为叶子都出现在同一层上，所以B树也是树高平衡的。另外,每个结点中关键码的个数为子树的个数减1。

B树是2-3树的推广,2-3树是一个3阶B树。通常B树中的一个结点的大小能够填满一个磁盘页,存储在B树中的指针实际上是包含其孩子结点的块号,每个结点一般允许100个或者更多个孩子。

2.1.2 B树查找

B树的查找类似于2-3树的查找,所不同的是B树的每个结点上是多关键码的有序表,在到达某个结点时,先在有序表中查找,若找到,则查找成功;否则,按照指针信息到相应的子树中查找。当到达叶子结点时,则说明树中没有对应的关键码,查找失败。

在B树上的查找过程是一个顺指针查找结点和在结点中查找关键码交叉进行的过程。比如,上图中查找关键码为53的记录。首先,从root指向的根结点a开始,根结点a 中只有一个关键码,且53大于它,因此,按根结点a的指针域A1到结点c去查找,c结点有两个关键码(43、78),而53大于43小于78,应按结点c指针域A1到结点g去查找,在结点g中顺序比较关键码,找到关键码53。

所以,在B树上进行查找包含两种基本操作:

(1)定位节点：在B树中查找结点;

(2)定位节点中的关键码：在结点中查找关键码。

由于B树通常存储在磁盘上,则前一个查找操作(指在B树中查找结点)是在磁盘上进行的,而后一个查找操作(指在结点中查找关键码)是在内存中进行的,即在磁盘上找到某结点后,先将结点的信息读入内存,然后再查找等于k的关键码。显然,在磁盘上进行一次查找比在内存中进行一次查找耗费的时间多得多,因此,在磁盘上进行查找的次数,即待查关键码所在结点在B树的层数,是决定B树查找效率的首要因素。

2.1.3 B树插入

B树的插入是2-3树插入的推广

假定要在m阶B树中插入关键码key,设n=m-1,即n为结点中关键码数目的最大值,B树的插入过程如下:

(1)定位:查找插人位置。由于是在终端结点中插入,因此要确定它属于哪个终端结点。定位的结果是返回了key所属终端结点的指针p。若p中的关键码个数小于n,则 直接插人关键码key;否则,结点p的关键码个数溢出,执行“分裂一提升”过程。

(2)分裂一提升:将结点p“分裂”成两个结点,分别是p1和p2,把中间的关键码k“提升”到父结点,并且k的左指针指向p1,右指针指向p2。如果父结点的关键码个数也溢出,则继续执行“分裂一提升”过程。显然,这种分裂可能一直上传,如果根结点也分裂了,则树的高度增加了一层 。

整个插入过程保证所有的结点至少是半满的。例如,当一个4阶B树的内部结点已满时,将会有5个子女。这个结点分裂成为两个结点,每个结点包含两个关键码,这样就 保持了B树的特性。下图给出了在3阶B树中进行插入的示例：

2.1.4 B树删除

B树的删除是2-3树删除的推广。

设在m阶B树中删除关键码key。首先要找到key的位置,即“定位”。定位的结果是返回了key所在结点的指针q,假定key是结点q中第i个关键码K,若结点q不是终结点,则用Ai所指的子树中的最小键值x来“替换”Ki。由于x所在结点一定是终端结点,这样,删除问题就归结为在终端结点中删除关键码。
如果终端结点中关键码的个数大于⌈m/2⌉-1,则可直接删除该关键码,如下图：

如果在终端结点中删除一个关键码后其关键码的个数不足⌈m/2⌉-2,则不符合m阶B树的要求,需要从兄弟结点借关键码或合并结点,以保证B树的特性。具体分两种情况：

(1)兄弟够借,查看相邻的兄弟结点,如果兄弟结点有足够多的记录(多于⌈m/2⌉),就从兄弟结点借来一个记录,将借来的关键码“上移”到被删结点的双亲结点中,同时将双亲结点中的相应关键码“下移”到被删结点中。这样做的目的是为了尽可能地延迟由于删除而引起的结点中关键码个数的下溢。

(2)兄弟不够借。如果没有一个兄弟结点可以把记录借给这个记录太少的被删结点,那么被删结点就必须把它的关键码让给一个兄弟结点,即执行“合并”操作,并且从树中把这个空结点删除。兄弟结点当然有空间,因为兄弟结点至多半满,合并后被删结点的双亲少了一个结点,所以要把双亲结点中的一个关键码“下移”到合并结点中。如果被删结点的双亲结点中的关键码的个数没有下溢,则合并过程结束;否则,双亲结点也要进行借关键码或合并结点。显然,合并过程可能会上传到根结点,如果根结点的两个子女合并到一起,则B树就会减少一层。

下图给出了在3阶B树中删除关键码时,出现被删结点中关键码个数发生下溢的情况以及处理示意图。

2.2 B+树（性质、插入、删除、查找、范围查找）

B+树是B树的变体，是由B树和索引顺序访问方法(ISAM,Indexed Sequential Access Methed)演变而来，B+树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树。在B+树中，所有记录都是按键值的大小顺序存放在同一层的叶子结点上，由各叶子节点指针进行拼接。

一棵m阶的B+树在结构上与m阶的B树相同,但在关键码的内部安排上有所不同。具体如下:

(1)具有m棵子树的结点含有m个关键码,即每一个关键码对应一棵子树;

(2)关键码K,是它所对应的子树的根结点中的最大(或最小)关键码;

(3)所有的终端结点中包含了全部关键码信息,及指向关键码记录的指针;

(4)各终端结点按关键码的大小次序链在一起,形成单链表,并设置头指针 与B_树类似,在B树中,结点内的关键码仍然有序排列,并且对同一结点内的任意 两个关键码K和K,若K,<K,则K,小于K,对应的子树中的所有关键码。

与二叉排序树和2-3树最显著的区别是B+树只在终端结点存储记录,内部结点存储关键码,但是这些关键码只是用于引导查找的。这意味着内部结点在结构上与终端结点有显著的区别。内部结点存储关键码用于引导查找,把每个关键码与一个指向子女结点 的指针相关联;终端结点存储实际记录,在B+树纯粹作为索引的情况下则存储关键码和指向实际记录的指针。一个B+树的终端结点一般链接起来,形成一个链表,这样,通过访问链表中的所有终端结点,就可以按照排序的顺序遍历全部记录。

例如,下图所示为一棵3阶的B+树,通常在B+树上有两个头指针,一个指向根结点,另一个指向关键码最小的终端结点。因此,可以对B+树进行两种查找操作:一种是 从最小关键码起顺序查找,另一种是从根结点开始随机查找。

在B+树上进行随机查找、插入和删除的过程基本上与B树类似。除了查找必须一直到达终端结点外,在一棵B树中的查找几乎与在一棵B树中的查找完全一样。即使在一个内部结点找到了待查找的关键码值,但它只是用来引导索引的,并不提供对实际记录的访问,所以

B+树查找：B+树中查找时,必须到达包含有该关键码值的终端结点。

B+树插入：B+树的插入仅在终端结点上进行,当结点中的关键码个数大于m时要分裂成两个结点,并且它们的双亲结点中应同时包含这两个结点中的最大关键码。

B+树删除：B+树的删除也仅在终端结点上进行,当终端结点中的最大关键码被删除时,其在非终端结点中的值可以作为一个“分界关键码”存在。若因删除而使结点中关键码的个数少于 时,和兄弟结点的合并过程和B树类似。

B+树范围查找：B+树特别适合范围查找。一旦找到了范围中的第一个记录,通过顺序处理结点中的 其余记录,然后继续下去,尽可能地深入终端结点,就可以找到范围中的全部记录。

B+树查找

先来看一个B+树，其高度为2，每页可存放4条记录，扇出(fan out)为5，如下图。
所有记录都在叶子节点上，并且都是顺序存放的，如果用户从最左边的叶子节点开始顺序遍历，可以得到所有键值的顺序排序：5、10、15、20、25、30、50、55、60、65、70、75、80、85、90。

2.3 小结

B树和B+树统称为B树,是需要插入、删除和关键码范围检索的应用程序的标准组织方法,解决了实现基于磁盘的检索时遇到的下列所有问题：

(1)B树总是树高平衡的,所有叶结点都在同一层;

(2)査找、插入和删除等操作只影响最少数量的结点(即磁盘页),因此性能很好;

(3)B树把相关的记录放在同一个磁盘页中,从而利用了访问局部性原理;

(4)B树保证树中至少有一定比例的结点是满的,这样能够改进空间的利用率,同时 在查找和更新操作期间减少对磁盘的读取次数。

三、B+树索引

3.1 索引有哪些数据结构

大家去设计索引的时候，会发现索引类型是可以选择的，包括Hash、B+、有序数组，如下：

3.2 B+树数据结构的优势（哈希表、二叉树、平衡二叉树、B树、B+树）？

总问题：从mysql索引考数据结构基础的内容？
回答：从二叉树、平衡二叉树、B树、B+树是一个不断升级的过程，最后选择B+树很合理，但是适用B+树：非叶子节点的检索 + 叶子节点中有序数组的二分法
加上hash表就是：非叶子节点的检索 + 叶子节点中hash数组

3.2.1 Hash索引

MySQL默认索引为什么是B+树索引，不是Hash索引？Hash索引两个缺点
缺点1：数据库使用哈希索引，所有字段值所对应的数组下标是哈希算法随机算出来的，所以可能出现哈希冲突。
缺点2：数据库使用哈希索引，只能快速的精确查询 =，但是不支持范围查询 。

那么对于这样一个索引结构，现在来执行下面的sql语句：

select * from table1 where name='csdn'
1

可以直接对‘csdn’按哈希算法算出来一个数组下标，然后可以直接从数据中取出数据并拿到所对应那一行数据的地址，进而查询那一行数据， 那么如果现在执行下面的sql语句：

select * from table1 where name < 'csdn'
1

则无能为力，因为哈希表的特点就是可以快速的精确查询，但是不支持范围查询。

如果做成了索引，那速度也是很慢的，要全部扫描。

那Hash表在哪些场景比较适合？
等值查询的场景，就只有KV（Key，Value）的情况，例如Redis、Memcached等这些NoSQL的中间件。

3.2.2 有序数组

你说的是无序的Hash表，那有没有有序的数据结构？
有序数组，它就比较优秀了呀，它在等值查询的和范围查询的时候都很Nice。可以用来做静态存储引擎啊，用来保存静态数据，例如你2019年的支付宝账单，2019年的淘宝购物记录等等都是很合适的，都是不会变动的历史数据。

有序数组优缺点：

有序数组适合静态数据的查找和范围查找(因为有序)，因为如果我们新增、删除的时候就会改变他的结构。因为有序数组底层是一个数组结构（底层数据结构只有两种：数组和链表，树和图是链表变式）你新增一个，那在你新增的位置后面所有的节点都会后移，成本很高。

3.2.3 二叉树做索引

第一，因为二叉树是有序的，所以是支持范围查询的。

3.2.4 平衡二叉树做索引

第一，因为二叉树是有序的，所以是支持范围查询的。
第二，因为时间复杂度是O(log(N))，为了维持这个时间复杂度，所以更新的时间复杂度也应该是O(log(N))。

因平衡二叉树做索引，因为索引也不只是在内存里面存储的，还是要落盘持久化的，如果数据多了，树高会很高，查询的成本就会随着树高的增加而增加（金手指：树高一层就要读磁盘一次）。

为了节约成本很多公司的磁盘还是采用的机械硬盘，这样一次千万级别的查询差不多就要10秒了，这谁顶得住啊？

3.2.5 用B树做索引

同样的元素，B树的表示要比完全平衡二叉树要“矮”，原因在于B树中的一个节点可以存储多个元素。

B树其实就已经是一个不错的数据结构，用来做索引效果还是不错的。

3.2.6 用B+树做索引

存储同样的元素，B+树和B树树高相同，但是，B+树的表示要比B树要“胖”，原因在于B+树中的非叶子节点会冗余一份在叶子节点中，并且叶子节点之间用指针相连。

问题：为什么最后选择B+树（二叉树、平衡二叉树、B树、B+树）？囊括各种数据结构的优缺点？

回答：
Hash不支持范围查询且字段对应的下标容易发生哈希冲突(两个缺点)；
有序数组适合查找和范围查找(因为有序)，但是不适合新增和删除；
二叉树解决了hash的范围查询问题，但是树高很高；
平衡二叉树解决了二叉树树高的问题，但是每一个节点都只能放一个元素；
B树解决了平衡二叉树每一个节点只能放一个元素的问题，一个节点放满足B树定义的多个元素，进一步解决树高的问题，磁盘IO效率提高了，减少访问磁盘的平均次数；
B+树相对于B树，解决树高没有改进，但是结构上有一个变化：B+树中的非叶子节点会冗余一份在叶子节点中(叶子节点之间用指针相连)，提高了范围查找的效率，提高了的原因也无非是会有指针指向下一个节点的叶子节点。

所以，Mysql选用B+树这种数据结构作为索引，可以提高查询索引时的磁盘IO效率，并且可以提高范围查询的效率，并且B+树里的元素也是有序的。

3.3 B+树中一个节点到底多大合适？

问题：B+树中一个节点到底多大合适？
回答：B+树中一个节点为一页或页的倍数最为合适。如果一个节点的大小小于1页，比如0.8页，那么读取这个节点的时候其实也会读出1页，造成资源的浪费。如果一个节点的大小大于1页，比如1.2页，那么读取这个节点的时候会读出2页，也会造成资源的浪费。所以为了不造成浪费，所以最后把一个节点的大小控制在1页、2页、3页、4页等倍数页大小最为合适。

问题：操作系统页的概念？
操作系统中，一个页大小是4KB，InnoDB中，一个页的大小是16KB，即相当于操作系统四个页的大小。Mysql的基本存储结构是页(记录都存在页里边)：

1、页间+页内：各个数据页可以组成一个双向链表，而每个数据页中的记录又可以组成一个单向链表(就是叶子节点指针相连)；
2、每个数据页都会为存储在它里面的记录生成一个页目录，以主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录；
3、以其他列(非主键)作为搜索条件：只能从最小记录开始依次遍历单链表中的每条记录。

如果我们写 select * from table1 where website='csdn’这样没有进行任何优化的sql语句，默认会这样做：

第一，定位到记录所在的页（注意：需要遍历双向链表，找到所在的页，时间复杂度为O(n)，因为各个数据页组成双向链表，使用了B+树索引后，时间复杂度为O(lgN)就可以定位到指定页了）

第二，从所在的页内中查找相应的记录（注意：由于不是根据主键查询，只能遍历所在页的单链表了，因为数据页中的记录组成单链表）

很明显，在数据量很大的情况下这样查找会很慢！看起来跟回表有点点像。

3.4 B+树作为索引，特征决定优势

特征1：B+Tree通常意味着所有的值都是按顺序存储的(存储在叶子节点里),并且每一个叶子页到根的距离相同。

特征2：适合查找，B+Tree索引取代全表扫描，能够加快访问数据的速度

B+Tree索引能够加快访问数据的速度,因为存储引擎不再需要进行全表扫描来获取需要的数据,取而代之的是从索引的根节点开始进行搜索，根节点存放了指向子节点的指针,存储引擎根据这些指针向下层查找。通过比较节点页的值和要查找的值可以找到合适的指针进入下层子节点,这些指针实际上定义了的上限和下限。最终存储引擎要么是找到对应的值,要么该记录不存在。

特征3：顺序存储适合范围查找

叶子节点比较特别,它们的指针指向的是被索引的数据,而不是节点页(ps:不同引擎的“指针”类型不同),树的深度和表的大小直接相关。B+树 对索引列是顺序组织存储的,所以很适合查找范围数据。例如,在一个基于文本域的索引树上,按字母顺序传递连续的值进行查找是非常合适的,所以像“找出所有以I到K开头的名字”这样的查找效率会非常高。

3.5 B+树索引的优势

请注意,索引对多个值进行排序的依据是CREATE TABLE语句中定义索引时列的顺序。例如，用户表中，两个人的姓和名都一样,则根据他们的出生日期来排列顺序。

可以使用B-Tree索引的查询类型。 B-Tree索引适用于全键值查找、键值范围查找、键前缀查找。 其中键前缀查找只适用于根据最左前缀的查找,前面所述的索引对如下类型的查询有效。

全键值查找(=号)
全值匹配指的是和索引中的所有列进行匹配,例如前面提到的索引可用干查找姓名为Cuba Allen、出生于1960-01-01的人。

键值范围查找(> < >= <= between and（相当于 >= AND <= 因此包含两端的值）)
例如前面提到的索引可用于查找姓在Aen和Barrymore之间的人,这里也只使用了索引的第一列。

匹配最左前缀
前面提到的索引可用于查找所有姓为Alen的人,即只使用索引的第一列。

匹配列前缀
也可以只匹配某一列的值的开头部分,例如前面提到的索引可用于查找所有以J开头的姓的人,这里也只使用了索引的第一列。

精确匹配某一列并范围匹配另外一列
前面提到的索引也可用于查找所有姓为Allen,并且名字是字母K开头(比如Kim、Karl等)的人,即第一列last_name全匹配,第二列first_nane范围匹配。

只访问索引的查询
B-Tree通常可以支持“只访问索引的查询”,即查询只需要访问索引,而无须访问数据行,后面我们将单独讨论这种“覆盖索引”的优化。

因为索引树中的节点是有序的。所以除了按值查找之外,索引还可以用于查询中的ORDER BY操作(按顺序查找),一般来说,如果B-Tree可以按照某种方式查找到值,那么也可以按照这种方式用于排序。所以,如果ORDER BY子句满足前面列出的几种查询类型,则这个索引也可以满足对应的排序需求。

3.6 B+树索引的不足

附：一些关于 B-Tree索引的限制
（1）如果不是按照索引的最左列开始查找,则无法使用索引。例如上面例子中的索引无法用于查找名字为Bill的人,也无法查找某个特定生日的人,因为这两列都不是最左数据列。类似地,也无法查找姓氏以某个字母结尾的人；
（2）不能跳过索引中的列,也就是说,前面所述的索引无法用于查找姓为 Smith并且在某个特定日期出生的人,如果不指定名(first_name),则 MySQL只能使用索引的第一列；
（3） 如果查询中有某个列的范围查询,则其右边所有列都无法使用索引优化查找。例如 有查询
WHERE last name=‘Smith’ AND first_name LIKE ‘J%’ AND dob=1976-12-23,
这个查询只能使用索引的前两列,因为这里LIKE是一个范围条件(但是服务器可以把其余列用于其他目的)。如果范围查询列值的数量有限,那么可以通过使用多个等于条件来代替范围条件。

到这里读者应该可以明白,前面提到的索引列的顺序是多么的重要：这些限制都和索引列的题序有关。

3.7 B+树索引四个特征

第一，降低树高(查找 lgN)：
（1）N叉树：B+树是以 N 叉树的形式存在的，树变胖，降低树高；
（2）平衡树：B+树使用平衡二叉树原理，最长程度上降低树高；
（3）B树：B+树一个节点存放多个数据，降低树高。
（4）B+树：从B树到B+树没有降低树高，但是树变胖了，原因在于B+树中的非叶子节点会冗余一份在叶子节点中，并且叶子节点之间用指针相连。

第二，有序(范围查找)：查找数据也不需要全表扫描了，顺着根节点层层往下查找能很快地找到我们的目标数据；

第三，程序局部性原理的磁盘预读：每个节点的大小即一个磁盘块的大小，一次 IO 会将一个页（每页包含多个磁盘块）的数据都读入（即磁盘预读，程序局部性原理:读到了某个值，很大可能这个值周围的数据也会被用到，干脆一起读入内存）；

第四，叶子节点指针链表连接，将随机IO变成顺序IO，不会再在内存中形成临时表：叶子节点通过指针的相互指向连接，能有效减少顺序遍历时的随机 IO，而且我们也可以看到，叶子节点都是按索引的顺序排序好的，这也意味着根据索引查找或排序都是排序好了的，不会再在内存中形成临时表。

四、哈希索引、全文索引

4.1 哈希索引

哈希索引基本散列表实现，只有精确匹配索引所有列的查询才有效。散列表（也称哈希表）是根据关键码值(Key value)而直接进行访问的数据结构，它让码值经过哈希函数的转换映射到散列表对应的位置上，查找效率非常高。

在 MySQL中,只有 Memory引擎显式支持哈希索引,这也是 Memory引擎表的默认索引类型, Memory引擎同时也支持 B+Tree索引,值得一提的是, Memory引擎是支持非唯一哈希索引的，这在数据库世界里面是比较与众不同的。如果多个列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希条目中。

假设我们对名字建立了哈希索引，则查找过程如下图所示：

哈希索引的工作过程：从上图左边看，对于Mysql中每一行数据，存储引擎都会对所有的索引列（上图左边中的 name 列，值为“张三”、“李四”、“王五”），经过哈希算法（即上图中间的矩形），计算一个哈希码（上图散列表的位置），散列表里的每个元素指向数据行的指针（再次反映了逻辑相邻不是物理存储相邻，B+树索引和哈希索引都是这样）。

从底层数据结构来说，B+树索引：使用的数据结构是B+树。哈希索引：使用的数据结构是哈希表。理论上来说，哈希索引比B+树索引更快，直接计算出来了，时间复杂度为O(1)，且索引自身只存储对应的哈希值，索引的结构十分紧凑，那么为什么InnoDB使用B+树作为默认索引。因为哈希索引有两个致命的弱点：

(1) 没有办法做范围查找，不支持排序，即只能完成精准查找，无法完成 < = <= between…and… 这样的范围查找，因为哈希值算出的是一个没有顺序的hash值，得到的 rowid 也是没有顺序。

(2) 容易造成哈希冲突，如果对 name 使用哈希索引，同名两条记录的计算出来的哈希值一样，就会哈希冲突。当出现哈希冲突的时候,存储引擎必须遍历链表中所有的行指针,逐行进行比较,直到找到所有符合条件的行。

（3）哈希索引也不支持部分索引列匹配查询，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。例如，在数据列(A,B)上建立哈希索引，如果查询只有数据列A，则无法使用该索引。

更多的时候，哈希表是与 B+ Tree等一起使用的，B+树范围查找 + 哈希表精准查找。在 InnoDB 引擎中就有一种名为「自适应哈希索引」的特殊索引。这种自适应哈希索引，当 innoDB 注意到某些索引值使用非常频繁时，就会内存中基于 B-Tree 索引之上再创建哈希索引，这样也就让 B+ 树索引也有了哈希索引的快速查找等优点，这是完全自动，内部的行为，用户无法控制或配置，不过如果有必要，可以关闭该功能。

自适应哈希索引将原来的 “B+树范围查找+叶子节点内二分法查找” 变为 “B+树范围查找+叶子节点内哈希查找”。

4.2 全文索引

全文索引是一种特殊类型的索引,它查找的是文本中的关键词,而不是直接比较索引中的值。当使用Blob或者Text这种大文本类型的时候，如果直接使用like搜索这个字段中的某些字符，不走索引，这个使用就要对这个字段使用全文索引。

全文搜索和其他几类索引的匹配方式完全不一样。它有许多需要注意的细节,如停用词、词干和复数、布尔搜索等,全文索引更类似于搜索引擎做的事情,而不是简单的WHERE条件匹配。在相同的列上同时创建全文索引和基于值的B-Tree索引不会有冲突,全文索引适用于 MATCH AGAINST操作,而不是普通的WHERE条件操作。

值得注意的是，MySQL默认实现的全文索引仅仅对于英文这样的自然语言好用，因为英文各个单词之间已经用空格分开，不需要做分词操作。但是对于中文这样非自然语言不好用，经常找不到，本地操作的话，还不如用like，项目开发中，一般使用ES或者Solr这样的站内索引引擎实现。所以，MySQL的全文索引和它的缓存层一样鸡肋，都没什么用，在使用中，缓存使用Redis或者Mongodb实现，查询大文本中的字符用ES或者Solr实现。

五、尾声

B+树索引、哈希索引、全文索引，完成了。

天天打码，天天进步！