索引介绍

    索引是帮助数据库高效获取数据的数据结构。在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用数据， 这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引。

    假设我们有存了100个 1~999的数字，在没有索引的情况下，数据库会对表全表扫描，如果我要查找的记录排在表的后面，那么就需要越过大半的记录才能查找到我需要的记录。此时的查找效率会很低。

    在这基础之上，如果有索引，将这些数据通过二分法插入一个二叉树中，此时我再查找这个数据，就不需要一条条记录地去比对了，此时100条记录最多查找7次就能够查找到我需要的记录，极大地提高了查找效率。(当然，数据库里的数据结构不是就只是简单的二叉树)

    当然，索引也不是只有优势没有劣势。

优势	劣势
提高数据检索的效率，降低数据库的IO成本	索引列也是要占用空间的
通过索引列对数据进行排序，降低数据排序的成本，降低CPU的消耗。	索引大大提高了查询效率，同时却也降低更新表的速度， 如过对表进行INSERT、UPDATE、DELETE时，效率会降低。

B树数据结构

    MySQL的索引是在存储引擎层实现的，不同的存储引擎有不同的索引结构，主要包含以下几种：

索引结构	描述
B+Tree索引	最常见的索引类型，大部分引擎都支持 B+ 树索引
Hash索引	底层数据结构是用哈希表实现的, 只有精确匹配索引列的查询才有效, 不支持范围查询
R-tree(空间索引）	空间索引是MyISAM引擎的一个特殊索引类型，主要用于地理空间数据类型，通常使用较少
Full-text(全文索引)	是一种通过建立倒排索引,快速匹配文档的方式。类似于Lucene,Solr,ES

    上面是MySQL中支持的所有索引，当然，没有特意指明的情况，索引一般都指B+Tree索引 

B-tree

    介绍B+Tree前，还要先介绍一下B-Tree结构。B-Tree，B树是一种多叉路衡查找树，相对于二叉树，B树每个节点可以有多个分支，即多叉。 以一颗最大度数 (一个节点中最多存储的指针数) 为5的b-tree为例，那这个B树每个节点最多存储4个key，5 个指针:

    B-tree的特点

1.n阶的B树，每一个节点最多存储n-1个key，对应n个指针

2.若当前节点存储的key数量到达5，就会裂变，中间元素向上分裂

(例如:一个末节点的key有88、89、95、96，而上一层的key为80、100、110。这个时候添加一个97到表里，97数据会先从根节点查找到该末节点，然后将其添加到该末节点，然后95会裂变，添加到上一层中，这就是裂变)

3.在B树中，非叶子节点和叶子节点都会存放数据

    这样一来，存储时使用b-tree，依旧有一定缺陷，也因此又衍生出了B+tree，也是大多数数据库主要使用的数据结构。

B-Tree的不足

    所有的非叶子节点和叶子节点都会同时存放数据和指针。在硬盘中，存储空间是被划分为一个个块的，而B-Tree中的数据和指针混杂分散在每一个节点中。

    IO操作时，读取数据会不连续。在查询多个连续数据时，若当前节点里没有查找完需要的数据，不能直接跳转到下一个节点，还需返回上一层节点找到下一个指针，再去访问下一个节点。底层的数据操作比较繁琐。

    在添加数据时，B-Tree还会进行裂变，但B-Tree裂变时不仅影响指针还会影响数据，cpu开销比较大。

B+tree

    为了改进B-Tree树的不足，又衍生出了B+Tree。B+Tree与B-Tree类似，但有很多不同，下面这是一个最大度数为4的B+Tree结构图:

    其中，蓝色框框圈起来的部分，也就是非叶子节点，仅起到索引数据的作用，只以key-value形式存放指针，不存放具体的数据。

    红色部分是存储数据的部分，也是该树的叶子节点 ，则存放所有具体的数据内容。并且每个叶子节点中，会存放一个指向下一个叶子节点的指针(但没有指向上一个叶子节点的指针)。

    B-Tree和B+Tree的区别：

1.所有的数据都会出现在叶子节点

2.叶子节点形成一个单向链表

3.非叶子节点仅仅起到索引数据作用，具体的数据都是在叶子节点存放的

为何B+Tree比B-Tree更适合实际中操作系统的文件索引和数据库索引

     1.B+Tree的磁盘读写代价更低。B+Tree的内部节点并没有指向关键字具体信息的指针。因此其内部节点相对BTree更小，如果把所有同一内部节点的关键字存放在同一个盘块中，那么盘块所能容纳的关键字数量也越多。一次性读取到内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了

     2.B+Tree的查询效率更加稳定。由于非叶子节点不是最终指向文件内容的节点，而是叶子节点中关键字的索引，所以任何关键字的查找都必须走一条从根节点到叶子节点的路。所有关键字的路径长度相同，导致每个数据的查询效率相当

MySQL中的B+Tree

    对比普通的B+Tree，MySQL在其基础上，添加了一个指向上一个叶子节点 (首尾相连) 的指针，也就是变成了一个双链表。

索引分类 

    在MySQL数据库，将索引的具体类型主要分为以下几类：主键索引、唯一索引、常规索引、全文索引。

分类	含义	特点	关键字
主键索引	针对于表中主键创建的索引	默认自动创建, 只能有一个	PRIMARY
唯一索引	避免同一个表中某数据列中的值重复	可以有多个	UNIQUE
常规索引	快速定位特定数据	可以有多个
全文索引	全文索引查找的是文本中的关键词，而不是比较索引中的值	可以有多个	FULLTEXT

而在在InnoDB存储引擎中，根据索引的存储形式，又可以分为以下两种

分类	含义	特点
聚集索引	将数据存储与索引放到了一块，索引结构的叶子节点保存了行数据	必须有,而且只有一个
二级索引	将数据与索引分开存储，索引结构的叶子节点关联的是对应的主键	可以存在多个

     聚集索引选取规则:

1.如果存在主键，主键索引就是聚集索引

2.如果不存在主键，将使用第一个唯一（UNIQUE）索引作为聚集索引

3.如果表没有主键，或没有合适的唯一索引，则InnoDB会自动生成一个rowid作为隐藏的聚集索引

聚集索引和二级索引的具体结构

    聚集索引的叶子节点下挂的是这一行的数据，二级索引的叶子节点下挂的是该字段值对应的主键值。

    在查询数据时，如果是通过二级索引查找数据。数据库系统会先在二级索引的目录里进行查找，获取到了对应主键值后，进行回表查询。也就拿着主键值，去聚集索引查询需要的数据。

    回表查询： 这种先到二级索引中查找数据，找到主键值，然后再到聚集索引中根据主键值，获取数据的方式，就称之为回表查询。

    在执行查询语句时，如果能够走聚集索引，就不必要走二级索引。

    在数据库查询语句优化时，注意走聚集索引也是一个重要的优化方向。