索引

索引(收集自互联网)

1.索引是什么

   索引，类似于书籍的目录，想找到一本书的某个特定的主题，需要先找到书的目录，定位对应的页码。MySQL 中存储引擎使用类似的方式进行查询，先去索引中查找对应的值，然后根据匹配的索引找到对应的数据行。

索引有什么好处？

提高数据的检索速度，降低数据库IO成本：使用索引的意义就是通过缩小表中需要查询的记录的数目从而加快搜索的速度。

降低数据排序的成本，降低CPU消耗：索引之所以查的快，是因为先将数据排好序，若该字段正好需要排序，则正好降低了排序的成本。

索引有什么坏处？

占用存储空间：索引实际上也是一张表，记录了主键与索引字段，一般以索引文件的形式存储在磁盘上。

降低更新表的速度：表的数据发生了变化，对应的索引也需要一起变更，从而减低的更新速度。否则索引指向的物理数据可能不对，这也是索引失效的原因之一。

 索引的使用场景？

1、对非常小的表，大部分情况下全表扫描效率更高。

2、对中大型表，索引非常有效。

3、特大型的表，建立和使用索引的代价随着增长，可以使用分区技术来解决。

 索引的类型？

索引，都是实现在存储引擎层的。主要有：

1、普通索引：最基本的索引，没有任何约束。

2、唯一索引：与普通索引类似，但具有唯一性约束。

3、主键索引：特殊的唯一索引，不允许有空值。（innodb主键索引的叶子节点存的是整行数据，也叫聚簇索引）

4、复合索引：将多个列组合在一起创建索引，可以覆盖多个列。

5、外键索引：只有InnoDB类型的表才可以使用外键索引，保证数据的一致性、完整性和实现级联操作。

6、全文索引：MySQL 自带的全文索引只能用于 InnoDB、MyISAM ，并且只能对英文进行全文检索，一般使用全文索引引擎。

7、二级索引：非主键索引叫二级索引，或者辅助索引（innodb与myisam叶子节点存储的东西不一致。注意区别）

其他定义：

覆盖索引：在查询里，索引已经覆盖了我们需要查询的数据，这样我们就不需要再回表了。叫做覆盖索引。

索引下推： 在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

2.索引原理-b树与b+树的区别

一，b树

b树（balance tree）和b+树应用在数据库索引，可以认为是m叉的多路平衡查找树，但是从理论上讲，二叉树查找速度和比较次数都是最小的，为什么不用二叉树呢？

因为我们要考虑磁盘IO的影响，它相对于内存来说是很慢的。数据库索引是存储在磁盘上的，当数据量大时，就不能把整个索引全部加载到内存了，只能逐一加载每一个磁盘页（对应索引树的节点）。所以我们要减少IO次数，对于树来说，IO次数就是树的高度，而“矮胖”就是b树的特征之一，它的每个节点最多包含m个孩子，m称为b树的阶，m的大小取决于磁盘页的大小。

一个M阶的b树具有如下几个特征：

1.每个结点最多有m-1个关键字。

2.根结点最少可以只有1个关键字。

3.非根结点至少有Math.ceil(m/2)-1个关键字。

4.每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。

5.所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。

有关b树的一些特性，注意与后面的b+树区分：

1.关键字集合分布在整颗树中；

2.任何一个关键字出现且只出现在一个结点中；

3.搜索有可能在非叶子结点结束；

4.其搜索性能等价于在关键字全集内做一次二分查找；

b树的查询：

如图是一个3阶b树，顺便讲一下查询元素5的过程：

1，第一次磁盘IO，把9所在节点读到内存，把目标数5和9比较，小，找小于9对应的节点；

2，第二次磁盘IO，还是读节点到内存，在内存中把5依次和2、6比较，定位到2、6中间区域对应的节点；

3，第三次磁盘IO就不上图了，跟第二步一样，然后就找到了目标5。

可以看到，b树在查询时的比较次数并不比二叉树少，尤其是节点中的数非常多时，但是内存的比较速度非常快，耗时可以忽略，所以只要树的高度低，IO少，就可以提高查询性能，这是b树的优势之一。

b树的插入元素操作：

  插入操作是指插入一条记录，即（key, value）的键值对。如果B树中已存在需要插入的键值对，则用需要插入的value替换旧的value。若B树不存在这个key,则一定是在叶子结点中进行插入操作。

1，根据要插入的key的值，找到叶子结点并插入。

2，判断当前结点key的个数是否小于等于m-1，若满足则结束，否则进行第3步。

3，以结点中间的key为中心分裂成左右两部分，然后将这个中间的key插入到父结点中，这个key的左子树指向分裂后的左半部分，这个key的右子支指向分裂后的右半部分，然后将当前结点指向父结点，继续进行第3步。

b树的删除元素操作：

  删除操作是指，根据key删除记录，如果B树中的记录中不存对应key的记录，则删除失败。 

1）如果当前需要删除的key位于非叶子结点上，则用后继key（这里的后继key均指后继记录的意思）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上，这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步

2）该结点key个数大于等于Math.ceil(m/2)-1，结束删除操作，否则执行第3步。

3）如果兄弟结点key个数大于Math.ceil(m/2)-1，则父结点中的key下移到该结点，兄弟结点中的一个key上移，删除操作结束。

否则，将父结点中的key下移与当前结点及它的兄弟结点中的key合并，形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针，指向这个新结点。然后当前结点的指针指向父结点，重复上第2步。

有些结点它可能即有左兄弟，又有右兄弟，那么我们任意选择一个兄弟结点进行操作即可。

参考：https://www.cnblogs.com/nullzx/p/8729425.html

二，b+树

 b+树，是b树的一种变体，查询性能更好。m阶的b+树的特征：

1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

b+树相比于b树的查询优势：

1.b+树的中间节点不保存数据，所以磁盘页能容纳更多节点元素，更“矮胖”；

2.b+树查询必须查找到叶子节点，b树只要匹配到即可不用管元素位置，因此b+树查找更稳定（并不慢）；

3.对于范围查找来说，b+树只需遍历叶子节点链表即可，b树却需要重复地中序遍历;

参考：https://www.jianshu.com/p/1f2560f0e87f

3.myisam与innodb索引的区别

一，MyISAM索引的实现

  MyISAM索引文件和数据文件是分离的，索引文件仅保存记录所在页的指针（物理位置），通过这些地址来读取页，进而读取被索引的行。下图是MyISAM的索引原理图：（为了简化，一个页内只存放了两条记录。）

      上图所提供的示例表字段有Col1（ID）、Col2(age)、Col3（name）三个，其中Col1为Primary Key（主键），上图很好地说明了树中叶子保存的是对应行的物理位置。通过该值，存储引擎能顺利地进行回表查询，得到一行完整记录。同时，每个叶子页也保存了指向下一个叶子页的指针。从而方便叶子节点的范围遍历。

      而对于二级索引，在 MyISAM存储引擎中以与上图同样的方式实现，可以看出MyISAM的索引文件仅仅保存数据记录的地址。

二，InnoDB索引的实现

1.聚集索引

   与 MyISAM相同的一点是，InnoDB 也采用 B+Tree这种数据结构来实现 B-Tree索引。而很大的区别在于，InnoDB 存储引擎采用“聚集索引”的数据存储方式实现B-Tree索引，所谓“聚集”，就是指数据行和相邻的键值紧凑地存储在一起，注意 InnoDB 只能聚集一个叶子页（16K）的记录（即聚集索引满足一定的范围的记录），因此包含相邻键值的记录可能会相距甚远。

注意: innodb来说,

1: 主键索引 既存储索引值,又在叶子中存储行的数据

2: 如果没有主键, 则会Unique key做主键

3: 如果没有unique,则系统生成一个内部的rowid做主键.

4: 像innodb中,主键的索引结构中,既存储了主键值,又存储了行数据,这种结构称为”聚簇索引”

      下图说明了 InnoDB聚集索引的实现方式，同时也体现了一张 innoDB表的结构，可以看到，InnoDB 中，主键索引和数据是一体的，没有分开。

  这种实现方式，给予了 InnoDB 按主键检索的超高性能。可以有目的性地选择聚集索引，比如一个邮件表，可以选择用户ID来聚集数据，这样只需要从磁盘读取较少并且连续的数据页就能获得某个id的用户全部的邮件，避免了读取分散页时所耗费的随机I/O

2.二级索引

    而对于二级索引，InnoDB采用的方式是在叶子页中保存主键值，通过这个主键值来回表（上图）查询到一条完整记录，因此按辅助索引检索实际上进行了二次查询，效率肯定是没有按照主键检索高的。下图是辅助索引的实现方式：

    由于每个二级索引都包含主键索引，因此，为了减小二级索引所占空间，我们通常希望 InnoDB 表中的主键索引尽量定义得小一些（值得一提的是，MySIAM会使用前缀压缩技术使得索引变小，而InnoDB按照原数据格式进行存储。），并且希望InnoDB的主键是自增长的，因为如果主键并非自增长，插入时，由于写入时乱序的，会使得插入效率变低。

4.innodb主键索引和普通索引的区别

如果语句是select * from T where ID=500，即主键查询方式，则只需要搜索ID这棵B+树；

如果语句是select * from T where k=5，即普通索引查询方式，则需要先搜索k索引树，得到ID的值为500，再到ID索引树搜索一次。这个过程称为回表。

也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。

5.普通索引和唯一索引的区别

从查询上来说：

•对于普通索引来说，查找到满足条件的第一个记录后，需要查找下一个记录，直到碰到第一个不满足条件的记录。

•对于唯一索引来说，由于索引定义了唯一性，查找到第一个满足条件的记录后，就会停止继续检索。

从更新上来说

1.如果目标页在内存中：

•对于唯一索引来说，找到3和5之间的位置，判断有没有冲突，插入这个值，语句执行结束；

•对于普通索引来说，找到3和5之间的位置，插入这个值，语句执行结束。

2.如果目标页在不在内存中：

•对于唯一索引来说，需要将数据页读入内存，判断到没有冲突，插入这个值，语句执行结束；

•对于普通索引来说，则是将更新记录在change buffer，语句执行就结束了。

从这里可以看到，查询上普通索引只是比唯一索引多了一个一次指针寻找和一次计算，由于数据是按页读取的，数据几乎都在内存中，所以性能相差不大。但从更新上来看，如果数据不在内存中，唯一索引需要将数据从磁盘上读取到内存中，这样会引发随机读，导致IO消耗增多，而普通索引可以利用changebuffer，IO上边要节省很多。性能相差会很多，所以如果可以在业务端保证数据的唯一性，那就可以使用普通索引。

唯一索引为什么不能使用changebuffer？

对于唯一索引来说，所有的更新操作都要先判断这个操作是否违反唯一性约束。比如，要插入(4,400)这个记录，就要先判断现在表中是否已经存在k=4的记录，而这必须要将数据页读入内存才能判断。如果都已经读入到内存了，那直接更新内存会更快，就没必要使用change buffer了。

6. MySQL 索引的“创建”原则？

1、最适合索引的列是出现在 WHERE 子句中的列，或连接子句中的列，而不是出现在 SELECT 关键字后的列。

2、索引列的基数越大，索引效果越好。https://blog.csdn.net/mingyundezuoan/article/details/79038989

3、根据情况创建复合索引，复合索引可以提高查询效率。因为复合索引的基数会更大。

4、避免创建过多的索引，索引会额外占用磁盘空间，降低写操作效率。

5、主键尽可能选择较短的数据类型，可以有效减少索引的磁盘占用提高查询效率。

6、对字符串进行索引，应该定制一个前缀长度，可以节省大量的索引空间。

7.索引的使用事项

1、应尽量避免在 WHERE 子句中使用 != 或 <> 操作符，否则将引擎放弃使用索引而进行全表扫描。优化器将无法通过索引来确定将要命中的行数,因此需要搜索该表的所有行。

注意，column IS NULL 也是不可以使用索引的。

2、应尽量避免在 WHERE 子句中使用 OR 来连接条件，否则将导致引擎放弃使用索引而进行全表扫描，如：SELECT id FROM t WHERE num = 10 OR num = 20 。

3、应尽量避免在 WHERE 子句中对字段进行表达式操作，这将导致引擎放弃使用索引而进行全表扫描。

4、应尽量避免在 WHERE 子句中对字段进行函数操作，这将导致引擎放弃使用索引而进行全表扫描。

5、不要在 WHERE 子句中的 = 左边进行函数、算术运算或其他表达式运算，否则系统将可能无法正确使用索引。

6、复合索引遵循前缀原则。

7、如果 MySQL 评估使用索引比全表扫描更慢，会放弃使用索引。如果此时想要索引，可以在语句中添加强制索引。

8、列类型是字符串类型，查询时一定要给值加引号，否则索引失效。

9、LIKE 查询，% 不能在前，因为无法使用索引。如果需要模糊匹配，可以使用全文索引。