MySQL——关于索引的总结

首先说说索引的 优点 ：最大的好处无疑就是提高查询效率。有的索引还能保证数据的唯一性，比如唯一索引。

而它的 坏处 也很明显：索引也是文件，我们在创建索引时，也会创建额外的文件，所以会占用一些硬盘空间。其次，索引也需要维护，我们在增加删除数据的时候，索引也需要去变化维护。当一个表的索引多了以后，资源消耗是很大的，所以必须结合实际业务再去确定给哪些列加索引。

再说说索引的基本结构。一说到这里肯定会脱口而出：B+树！了解B+树前先要了解二叉查找树和二叉平衡树。 二叉查找树 ：左节点比父节点小，右节点比父节点大，所以二叉查找树的中序遍历就是树的各个节点从小到大的排序。 二叉平衡树 ：左右子树高度差不能大于1。B+树就是结合了它们的特点，当然，不一定是二叉树。

为什么要有二叉查找树的特点？？ 因为查找效率快，二分查找在这种结构下，查找效率是很快的。 那为什么要有平衡树的特点呢？ 试想，如果不维护一颗树的平衡性，当插入一些数据后，树的形态有可能变得很极端，比如左子树一个数据没有，而全在右子树上，这种情况下，二分查找和遍历有什么区别呢？而就是因为这些特点需要去维护，所以就有了上面提到的缺点，当索引很多后，反而增加了系统的负担。

接着说B+树。 它的结构如下 ：

可以发现，叶子节点其实是一个 双向循环链表 ，这种结构的好处就是，在范围查询的时候，我只用找到一个数据，就可以直接返回剩余的数据了。比如找小于30的，只用找到30，其余的直接通过叶子节点间的指针就可以找到。再说说其他特点： 数据只存在于叶子节点 。当叶子节点满了，如果再添加数据，就会拆分叶子节点，父节点就多了个子节点。如果父节点的位置也满了，就会扩充高度，就是拆分父节点，如25 50 75拆分成：25为左子树，75为右子树，50变成新的头节点，此时B+树的高度变成了3。它们的扩充的规律如下表，Leaf Page是叶子节点，index Page是非叶子节点。

再说说B树 ，B树相比较B+树，它所有节点都存放数据，所以在查找数据时，B树有可能没到达叶子节点就结束了。再者，B树的叶子节点间不存在指针。

最后说说Hash索引 ，相较于B+树，Hash索引最大的优点就是查找数据快。但是Hash索引最大的问题就是不支持范围查询。试想，如果查询小于30的数据，hash函数是根据数据的值找到其对应的位置，谁又知道小于30的有哪几个数据。而B+树正好相反，范围查询是它的强项。

附录： Hash到底是啥？？ 哈希中文名散列，哈希只是它的音译。 为啥都说Hash快？？ 首先有一块哈希表（散列表），它的数据结构是个数组，一个任意长度的数据通过hash函数都可以变成一个固定长度的数据，叫hash值。然后通过hash值确定在数组中的位置，相同数据的hash值是相同的，所以我们存储一个数据以后，只需O(1)的时间复杂度就可以找到数据。 那hash函数又是啥？？ 算术运算或位运算，很多应用里都有hash函数，但实际运算过程大不一样。这是Java里String的hashCode方法：

publicint hashCode() {

}

还有一个问题，hash函数计算出来的hash值有可能存在碰撞，即两个不同的数据可能存在相同的hash值，在MySQL或其他的应用中，如Java的HashMap等，如果存在碰撞就会以当前数组位置为头节点，转变成一个链表。

说到这里也清楚了为啥Java中引用类型要同时重写hashCode和equals了。两个对象，实例就算一模一样，它们的hash值也不相等， 为啥不相等？？ 默认的Object的hashCode方法会根据对象来计算hash值的，实例相同，但它们还是两个不同的对象啊，所以我们重写hashCode时，最简单的方法就是调用Object的hashCode方法，然后传入该引用类型的属性，让hashCode方法只根据这几个属性来计算，那么实例相同的话，它们的hash值也会相等。等hashCode比较完后，如果相等再比较实例内容，也就是equals，确保不是hash碰撞。

索引的分类

如果我们指定了一个主键，那么这个主键就是主键索引。如果我们没有指定，Mysql就会自动找一个非空的唯一索引当主键。如果没有这种字段，Mysql就会创建一个大小为6字节的自增主键。如果有多个非空的唯一索引，那么就让第一个定义为唯一索引的字段当主键，注意，是第一个定义，而不是建表时出现在前面的。

对于辅助索引来说，它们的B+树结构稍微有点特殊，它们的叶子节点存储的是主键，而不是整个数据。所以在大部分情况下，使用辅助索引查找数据，需要二次查找。但并不是所有情况都需要二次查找。比如查找的数据正好就是当前索引字段的值，那么直接返回就行。这里提一句，B+树的key就是对应索引字段的内容。

而辅助索引又有一些分类：唯一索引：不能出现重复的值，也算一种约束。普通索引：可以重复、可以为空，一般就是查询时用到。前缀索引：只适用于字符串类型数据，对字符串前几个字符创建索引。全文索引：作用是检测大文本数据中某个关键字，这也是搜索引擎的一种技术。

注意，聚集索引、非聚集索引和前面几个索引的分类并不是一个层面上的。上面的几个分类是从索引的作用来分析的。聚集、非聚集索引是从索引文件上区分的。主键索引就属于聚集索引，即索引和数据存放在一起，叶子节点存放的就是数据。数据表的.idb文件就是存放该表的索引和数据。

辅助索引属于非聚集索引，说到这也就明白了。索引和数据不存放在一起的就是非聚集索引。在MYISAM引擎中，数据表的.MYI文件包含了表的索引， 该表的 叶子节点存储索引和索引对应数据的指针，指向.MYD文件的数据。

索引的几点使用经验

经常被查询的字段；经常作为条件查询的字段；经常用于外键连接或普通的连表查询时进行相等比较字段；不为null的字段；如果是多条件查询，最好创建联合索引，因为联合索引只有一个索引文件。

经常被更新的字段、不经常被查询的字段、存在相同功能的字段

常见的索引类型：哈希表、有序数组、搜索树。

mysql之普通索引和唯一索引。

执行查询的语句是 select id from T where k=5

这个查询语句在索引树上查找的过程，先是通过 B+ 树从树根开始，按层搜索到叶子节点，也就是图中右下角的这个数据页，然后可以认为数据页内部通过二分法来定位记录。

InnoDB的索引组织结构：

change buffer:持久化的数据。InnoDB将更新 *** 作缓存在 change buffer中,也就是说,change buffer 在内存中有拷贝，也会被写入到磁盘，主要节省的则是随机读磁盘的IO消耗。

change buffer 只限于用在普通索引的场景下，而不适用于唯一索引.

merge:将 change buffer 中的 *** 作应用到原数据页，得到最新结果的过程。

merge执行流程：

1、从磁盘读入数据页到内存

2、从change buffer里找出这个数据页的change buffer记录，依次应用，得到新版数据页

3、写redo log,这个redo log包含了数据的变更和change buffer的变更。

change buffer 用的是 buffer pool 里的内存，因此不能无限增大。change buffer 的大小，可以通过参数 innodb_change_buffer_max_size=50 表示 change buffer 的大小最多只能占用 buffer pool 的 50%。

如果要在这张表中插入一个新记录 (4,400) 的话，InnoDB 的处理流程是怎样的。

第一种情况是，这个记录要更新的目标页在内存中

这时，InnoDB 的处理流程如下：

第二种情况是，这个记录要更新的目标页不在内存中

这时，InnoDB 的处理流程如下：

mysql>insert into t(id,k) values(id1,k1),(id2,k2)当前 k 索引树的状态，查找到位置后，k1 所在的数据页在内存 (InnoDB buffer pool) 中，k2 所在的数据页不在内存中。

分析这条更新语句，你会发现它涉及了四个部分：内存、redo log（ib_log_fileX）、 数据表空间（t.ibd）、系统表空间（ibdata1）。这条更新语句做了如下的 *** 作（按照图中的数字顺序）：

带change buffer的更新过程：

select * from t where k in (k1, k2) ,如果读语句发生在更新语句后不久，内存中的数据都还在，那么此时的这两个读 *** 作就与系统表空间（ibdata1）和 redo log（ib_log_fileX）无关了.

[toc]

在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的，本文主要讨论是MyISAM和InnoDB两个存储引擎的B+Tree索引的实现方式。

MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址，下面是MyISAM索引的原理图：

上图是一个MyISAM表的主索引示意，可以看出MyISAM的索引文件仅仅保存数据记录的地址，在MyIASM中，主索引和辅助索引在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。B+Tree的所有叶子节点包含所有关键字且按照升序排列的。

MyISAM表的索引和数据是分离的，索引保存在“表名.MYI”文件内，而数据保存在“表名.MYD”中。

MyISAM的索引方式也叫做 非聚集 的，之所以这么称呼是为了与InnoDB的聚集索引区分。

虽然InnoDB也使用B+Tree作为索引结构，但是具体实现方式却与MyISAM截然不同。

第一个重大区别是InnoDB的数据文件本身就是索引文件，从上文知道MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录地址，而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录，这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

上图是InnoDB主索引(同时也是数据文件)的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做 聚集索引 。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键(MyISAM可以没有)，如果没有显示指定，则MySQL系统会自动选择一个唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段为主键，这个字段长度为6字节，类型为长整形。

第二个与MyISAM索引的不同时InnoDB的辅助索引data域存储相应记录主键值而不是地址，换句话说，InnoDB的所有辅助索引都引用主键作为data域，例如，下图定义在col3上的辅助索引：

这里的英文字符的ASCII码作为比较准则。聚集索引这种方式使得按照主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键索引到主索引中检索获取记录。

了解不同存储引擎的索引实现对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白不建议使用过长的字段作为主键， 因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变的更大 ，在例如， 用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree非单调的主键会造成在插入新纪录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择

ES的索引不是B+Tree树，而是倒排索引，ES的倒排索引由 Term index，Term Dictionary和Posting List 组成的。

有倒排索引(inverted index)就用正排索引(forward index)，正排索引就是文档(Document)和他字段Fields正向对应的关系对应表如下：

那么倒排索引是字段Field和拥有这个Field的文档对应的关系如下：

Sex字段：

Age字段：

Jack、lucy或者17，18叫做term，而[1,3]就是Posting list。Posting list就是一个int数组，存储了所有包含某个term的文档id，那么什么是term index和term dictionary？

如上如果name字段很多个term，比如Carla,Sara,Elin,Ada,Patty,Kate,Selena，如果按照这样的顺序排列，找出某个特定的term一定很慢，因为term没有排序，需要全部过滤一遍，才能找出特定的term。排序之后就变成了：Ada,Carla,Elin,Kate,Patty,Sara,Selena。

这样就可以使用二分法的方式，比全遍历更快的找出目标的term，如果组织这些term的方式就是 term dictionary ，意思就是term的字典，有了term dictionary之后，就可以用比较少的比较次数和磁盘读次数查找目标。但是磁盘的随机读 *** 作仍然是非常昂贵的，所以尽量少的读磁盘，有必要把一些数据缓存到内存里，但是整个Term dictionary本身又太大了，无法完整的放到内存中，于是就有了term index，Term index有点像一本字典的打的章节表。比如：

A开头的term ……………. Xxx页

C开头的term ……………. Xxx页

E开头的term ……………. Xxx页

如果所有的term都是英文字符的话，可能这个term index就真的是26个英文字符表构成了。但是实际情况是，term未必都是英文字符，term可以是任意的byte数组。而且26个英文字符未必是每一个字符都有均等的term，比如x字符开头的term可能一个都没有，而s开头的term又特别多，实际的term index是一颗字典树(trie 树)：

上面例子是一个包含A", "to", "tea", "ted", "ten", "i", "in", 和 "inn" 的trie树。这棵树不会包含所有的term，他包含的是term的一些 前缀 ，通过term index可以快速定位到term dictionary的某个offest，然后从这个位置在往后顺序查找，再加上一些压缩技术，Term index的尺寸可以只有所有的term的尺寸的十分之一，用内存缓存整个term index变成可能，整体上来说就是这样的效果：

由Term index到Term Dictionary，再到posting list，通过某个字段的关键字去查询结果的过程比较清楚了，通过多个关键字的posting list进行and或者or进行交集并集的查询也简单了( 倒排索引介绍了交集并集的过程 )

对比MySQL的B+Tree索引原理，可以发现：

---