索引是什么

• MySQL中的索引是一种数据结构, 他可以帮助我们在数据库追上快速的查询到对应的记录. 一般我们查询表里面的记录是一条一条遍历来查询的, 而有了索引我们就不用遍历整个数据表来查询. 对查询速度提升了许多.
• 就好比我们书籍的目录, 如果我们想看关于挖宝藏的内容, 我们就可以看看书籍目录里面比如"xx宝藏遗址" 之类的标题, 我们就可以看到对应的页数, 直接翻到对应的页数.

优点和缺点

优点:

• 加快了查找记录的速度

缺点:

• 索引需要占 磁盘空间 ，除了数据表占数据空间之外，每一个索引还要占一定的物理空间， 存储在磁盘上，如果有大量的索引，索引文件就可能比数据文件更快达到最大文件尺寸。
• 虽然索引大大提高了査询速度，同时却会 降低更新表的速度 。当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。

B树和B+树

前面说了, 索引是MySQL中的一个数据结构, 那他使用的是那个数据结构呢? 好像查询速度比较快的就只有哈希表(o(1)查询速度)和红黑树(logn)这两个数据结构查询的速度快吧. 很可惜不是他们两个.

红黑树和哈希表存储数据的局限

• 哈希表之所以不适合作为索引的数据结构, 其主要原因就是不支持范围查询. 假设有几本书定价为10, 20, 40 , 60, 80, 100元, 他们通过哈希函数定址到同一个0号书架或者分散到不同的书架. 那么现在我们要去寻找50 - 100元之间的书, 你不知道这些书到底在那个书架. 他们有可能在同一个书架也可能在不同的书架, (哈希函数并不支持范围映射, 这里你通过哈希函数找到0, 可能还存在30 % 10 = 0, 30也在0号书架), 所以哈希表不能支持范围查询, 而我们的索引通常会会有查询某个范围数据的需求.
• 红黑树虽然支持范围查询, (左小跟右大跟), 但是红黑树是一个二叉搜索树, 他一个节点只有两个分支, 也就是每层的节点最多是2^n - 1次方, 这就导致存在数据库里面的大量数据会导致红黑树的高度非常高, 如果我们要进行查询每个数据, 我们有可能就会访问节点访问很多次. 在检索数据时，每次访问某个节点的⼦节点时都会发⽣⼀次磁盘IO，⽽在整个数据库系统中，IO是性能的瓶颈，减少IO次数可以有效的提升性能. 所以红黑树也不适合当索引的数据结构.

B树

• B树的分支树是节点N个key值的N + 1条边, 例如第一个节点有4个, 那么这个节点就有5条分支.
• B树的非叶子节点也有可能存储数据, 所以他的所有节点都有可能存储数据.

这里我们要进行查找40 - 60之间的数据, 这时候我们找到40的右分支, 找到43, 48. 这个时候我们又要回溯到根节点看到50也满足, 然后又去找到他的右分支.找到55这个满足条件的数据. 结果又要回溯到根节点, 发现根节点60这值也满足

• 可以看到我们进行范围查找的时候, 由于B树的数据都是分散存储在各个节点. 我们进行范围查找的时候需要警察进行回溯操作. 需要不断 “回溯根节点→跳转子节点→再回溯→再跳转”，像走迷宫一样，效率极低。这个效率和全部遍历差不了多少, 所以B树也不太适合作为索引的数据结构.

B+树

• B + 树也是一个 N 叉搜索树
• 每个节点上有 N 个值，划分出 N 个区间 (不是 N + 1 个), 期中最后一个元素表示当前子树的最大值 (也可以约定，第一个元素是最小值…)
• 每个子节点中，也可以包含 N 个值，同时会把父节点中对应最大值，放过来==> 最终效果，叶子节点，就是完整的数据集合
• 叶子节点通过双向链表连接起来, 这样我们就可以遍历整个链表就能找到完整的数据集合, 非常适合范围查找.

B + 树相比于 B 树的优势:

1. 叶子节点是数据全集，并且用链表连接，非常方便，进行范围查询了
2. 所有的数据都是在叶子上，使得叶子节点才存储完整的数据行，非叶子节点，只需要存储 索引 key 值即可,此时意味着非叶子节点占用空间较小，更适合在内存中缓存
3. 每次查询，都是需要查询到叶子，才能够完成查询的。中间经历的过程是差不多开销的～～(比较次数是相当的) ==> 查询的开销比较稳定, 比如我们查找1, 5范围数据, 和12, 15范围数据都是遍历到叶子节点, 这个查询效率是大差不差的.很稳定, 稳定其实是非常好的优
4. 不需要像B树那样一直回溯, 因为数据全集就在叶子节点, 我们只需要遍历叶子节点这个链表即可.

MySQL中的页

页是什么

页其实就是我们B+树上的节点, 这里又分为数据页和索引页. 数据页对应叶子节点, 存储若干个数据行. 索引页对应非叶子节点, 存储key和子节点的位置(也是一个页)

• 页默认⼤⼩为16KB，

为什么要使用页

因为我们数据库读取硬盘中的数据至少要读取一页, 页里面我们上面说了, 可能存储若干个数据行. 这个又因为我们有一个叫局部性原理的东西: 根据经验如果我们读取了硬盘中的一部分数据, 那么他旁边的数据我们也可能会读取. 那么使用页就会把旁边的一部分数据也存在同一个页中, 这个时候我们把这旁边的数据也读取出来了, 我们就不需要再去硬盘读取那部分数据了. 减少了硬盘的IO次数.

页的结构

• 从这张图我们可以看出来, 页是由页头+数据行+页尾构成的, 至于其他的具体内容, 我们在数据库高阶进行讲解.
  

三层树高的B+树可以存放多少条记录

• B+树的每个节点是一个页, 非叶子节点是索引页, 叶子节点是数据页
• 一页默认大小是16kb
• 索引页通常存储key(索引值) 和下一个子节点的位置 , 这里我们设key值是bigint类型占8个字节, 下一个页节点位置的指针占4个字节. 所以我们一个数据组是14个字节, 我们一页16kb = 16384个字节, 可以存储16484 / 14 = 1170条这样的数据组.
• 那么我们根节点就有1170个这样的数据组, 就有1170个页节点, 第二层1170个节点每个节点也可以存储1170个这样的数据组. 所以单个节点就有1170个分支, 1170个页节点就是1170 * 1170个 = 136w个页节点
• 到了第3层数据页, 就有了136w个节点, 数据页存储若干个数据行, 假设我们这里的数据行占1kb(实际是多少要看表结构), 我们一个数据页节点默认大小是16kb, 那么我们1个数据页节点就能存储16条数据, 我们有136w个页节点, 就能存储136w * 16 = 2000w条数据(这里忽略了页头页尾这些属性, 他们占太少字节了)
• 综上, 我们3层树高的B+树大概可以存放2000w条数据

其他要注意的是, 我们如果单个表的行数超过了2000w, 继续增加数据就可能让B+树的高度增加, 查询开销就有可能增加了. 这个时候我们就要考虑是否对这么大的表进行拆分来提升查询性能.

索引的分类

主键索引

创建主键的时候, 数据库自动创建的索引. 如果表中本身有主键, 自然就有主键索引. 如果表里面没有主键, 其实数据库会自动创建"隐藏列", 作为主键, 根据隐藏列设定索引.

普通索引

• 最基本的索引类型，没有唯⼀性的限制。
• 可能为多列创建组合索引，称为复合索引或组全索引

唯⼀索引

• 当在⼀个表上定义⼀个唯⼀键 UNQUE 时，⾃动创建唯⼀索引。
• 与普通索引类似，但区别在于唯⼀索引的列不允许有重复值。

全⽂索引

• 基于⽂本列(CHAR、VARCHAR或TEXT列)上创建，以加快对这些列中包含的数据查询和DML操作
• ⽤于全⽂搜索，仅MyISAM和InnoDB引擎⽀持。

聚集索引和非聚集索引(重要)

• 聚集索引也叫做聚簇索引.
• 前面的主键索引就是一个聚簇索引, 他对的叶子结点是保存了所有的数据行. 整个数据表就是通过聚簇索引来表示的
  
• 非聚集索引也叫做非聚簇索引, 假设我们有一个数据表student(id, name, sex, age), id是一个聚簇索引如上图表示. 现在用name列创建一个非聚簇索引.
  
• 为了节省空间, 我们不可能每个列的索引(B+树)都把数据行存储在叶子节点, 这里我们非聚簇索引(B+树)的叶子节点存储的就不是全部数据行行了, 而是保存对应数据行的主键id(主键索引存储的数据行)
• 那么针对name进行查询的时候, 我们不是直接查询到数据行, 而是查询到数据行对应的主键id, 然后再去主键索引中, 查一遍, 得到最终对的数据行(这个再查一遍的操作也叫做回表操作)

注意: 不管是聚簇索引和是非聚簇索引, 我们都有一个前提条件就是要使用MySQL中的innoDB这样的存储引擎, 如果其他的存储引擎有可能主键索引也是非聚簇索引.

• 那么存储引擎是什么呢? 存储引擎就是负责维护硬盘上数据存储的结构的模块. 对于MySQL来说, 最常用的存储引擎就是InnoDB

索引覆盖

• 当⼀个select语句使⽤了普通索引且查询列表中的列刚好是创建普通索引时的所有或部分列，这时
  就可以直接返回数据，⽽不⽤回表查询，这样的现象称为索引覆盖
• 就比如说我们select name from student, 那么我们不是查询整个数据行, 我们就可以在普通索引(B+树)的叶子节点就可以找到, 就不需要去主键索引(聚簇索引)哪里去找, 即不进行回表操作. 这个就叫做索引覆盖.

创建索引

自动创建

• 当我们为⼀张表加主键约束(Primary key)，外键约束(Foreign Key)，唯⼀约束(Unique)时，
  MySQL会为对应的的列⾃动创建⼀个索引
• 如果表不指定任何约束时，MySQL会⾃动为每⼀列⽣成⼀个索引并⽤ ROW_ID 进⾏标识(前面说了不创建主键也有一个隐藏列作为主键索引)
• 这里创建主键, 自动创建
  
• 创建外键约束和唯一约束自动创建的索引

• 这里classID这个列的索引的意义就是为了针对父表class进行修改/删除操作的时候, 需要根据classID在子表student进行查询, 看他存不存在如果存在则不能进行修改/删除操作, 即子表约束了父表.
• 唯一索引也就是创建唯一约束自动创建的.

手动创建

• create index 索引名 on 表名(列名)
  
• 这样我们的student表又增加了一个索引

创建复合索引

• 复合索引就是先按第一列查, 如果第一列相同了, 再去按照第二列来查找

查看索引

索引的一些注意事项

• 索引应该创建在⾼频查询的列上
• 索引需要占⽤额外的存储空间
• 创建过多或不合理的索引会导致性能下降，需要谨慎选择和规划索引(索引会去创建B+树, 如果数据多了, 是会影响性能的)
• 对表进⾏插⼊、更新和删除操作时，同时也会修索引，可能会影响性能