【面试题】MySQL索引相关知识点

1.什么是索引

索引是存储引擎快速查找记录的一种数据结构，就类似书的目录，通过目录可以快速的查找到想要查找的内容

---

2.索引的特点

• 特点：索引是基于数据引擎的，不同的数据引擎实现索引的方式不一定相同

• 好处：通过索引，可以降低磁盘IO的次数，从而加快查找的效率

• 坏处：

  • 创建索引和维护索引要耗费时间 ，并且随着数据量的增加，所耗费的时间也会增加。
  • 大量的索引，索引文件就可能比数据文件更快达到最大文件尺寸。（innoDB .ida MyISAM myd数据 myi索引）
  • 虽然索引大大提高了查询速度，同时却会降低更新表的速度 。当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。因此，选择使用索引时，需要综合考虑索引的优点和缺点。

---

3.采用B+树作为索引以后查询一条记录的过程

• 首先在根节点的数据页中，根据每一页里面的页目录（占用连续存储空间），进行二分查找，找到其对应的二级目录页。
• 在二级目录页中采用相同的方法进行查找。直到查找到叶子节点。
• 在叶子节点中，使用二分查找法查找到对应的记录。

---

4.B+树索引的特点

• 所有节点都存放数据。叶子节点存放用户的记录，非叶子节点用来存放目录项。
• 叶子节点之间通过双链表连接，叶子内部采用单链表连接

---

5.聚簇索引

• 聚簇索引指的是用户存储的数据都存储在叶子节点上的索引。即索引即数据，数据即索引。
• 常见的有InnoDB中的主键索引就是聚簇索引。

存储内容

• 非叶子节点存储页号以及对应页中主键的最小值。
• 叶子节点存放记录的全部信息

优点：

• 对于使用主键索引进行查找数据的时候相应速度很快，因为数据都已经存储在叶子节点上了
• 对于排序和范围查找都很快。因为本身就是有序的，而且由于数据都在叶子节点，那么直接遍历叶子节点组成的双链表即可。同时减少了大量的IO操作。

缺点：

• 插入速度依赖于插入顺序。如果不按照主键递增顺序插入，那么就会产生页分裂，严重降低插入速度。
• 更新主键的代价很高。可能会产生大量元素的移动。
• 二级索引在访问的时候需要回表操作。

限制

• 由于物理存储方式的限制，同一个表只能有一个聚簇索引。

---

6.二级索引 非聚簇索引

• 聚簇索引仅仅通过主键检索的时候才会生效，如果想按照别的字段进行检索的话，那么就需要建立非聚簇索引了。

存储内容

• 非叶子节点存储的是索引列的信息以及页号和对应页的最小主键值(为了防止索引列相同时无法判断)
• 叶子节点存储的是索引值，以及对应的主键值，用于回表操作。

对比

1. 聚簇索引的叶子节点存储的就是我们的数据记录，非聚簇索引的叶子节点存储的是数据位置。非聚簇索引不会影响数据表的物理存储顺序。
2. 一个表只能有一个聚簇索引，因为只能有一种排序存储的方式，但可以有多个非聚簇索引，也就是多个索引目录提供数据检索。
3. 使用聚簇索引的时候，数据的查询效率高，但如果对数据进行插入，删除，更新等操作，效率会比非聚簇索引低。

3.联合索引

• 联合索引本质上也是二级索引：先把各个记录和页按照c2列进行排序。

• 在记录的c2列相同的情况下，采用c3列进行排序

• 先按照C2排序，C2相同按照C3排序

---

7.InnoDB二叉树索引的两个特点

根节点万年不变

• 为根节点创建一个数据页，存放根节点，成为根页面。
• 当向表中插入数据时，直接将数据存放在根节点。
• 当根节点存储满了以后，再次插入数据会首先创建一个新的页面，将根节点的内容复制到这个新页面中，然后再创建一个新页面用来存放新插入的值。最后根节点变成目录节点。
• 当根节点中的目录项存满以后，再次插入新的目录项会像上一步一样，创建新数据页，将目录项复制到新数据页中，根节点变成了目录项的目录项。
• 从始至终，根节点的位置都不会发生变化，发生变化的只是里面存储的内容会变。

内节点目录项记录的唯一性

• 在非聚簇索引中，某些字段可能会重复，导致非聚簇索引中出现了除了页号以外的其他字段都相同的节点，这样在查找的时候就会出现不知道应该走哪一个节点的问题。因此实际上，在非聚簇索引的每一个节点中，还会添加主键字段。

---

8.MyISAM索引的原理

• MyISAM引擎的索引和数据是分离的，在存储数据时直接将文件写入到磁盘中。
• MyISAM会按照主键值创建索引，索引的叶子节点存储的是当前记录所在磁盘的地址。
• MyISAM实现了索引与数据的分离，因此在磁盘中会创建myi和myd两个文件
• MyISAM中只有非聚簇索引。

---

9.InnoDB和MyISAM的区别

• InnoDB中包含聚簇索引和非聚簇索引两种，在按照主键进行查询的时候，查找一次就可以查找到结果；MyISAM中所有的索引都是非聚簇索引，查询所有的数据都需要进行回表操作。

• InnoDB中索引和数据是在一起的，底层存储文件为ibd；MyISAM中数据和索引是分离的，分别存储为myi和myd两个文件

• InnoDB的索引叶子节点中存储的是数据；MyISAM中存储的是数据存储的地址

• MyISAM的回表速度很快，因为是直接通过地址访问；而InnoDB需要根据主键再次去聚簇索引中取数据，因此速度慢一些

• InnoDB必须有主键

InnoDB

• 支持事务，支持索引，支持行锁，在并发状态下仅所行，大幅提高并发性。提供外键约束

• 不保存表的行数，每次查询需要遍历整个表

• 主要为海量数据的最大性能设计

• 崩溃后可以安全的恢复

MyIASM

• 不支持事务管理，不支持外键，不支持行锁。在增删改的时候，会直接锁住整个表，导致效率低下。
• 保存了表的行数，在查询表的行数时不需要遍历整个表，效率高
• 数据量比较小的情况下效率较高
• 由于不支持事务，所以在崩溃后无法安全的恢复数据

---

10.索引的代价

• 空间上：会占用大量的存储空间
• 时间上：在增删改的时候，由于使用了索引，会导致增删改的时候效率不高。

---

11.可以成为索引的数据结构有什么，分别有什么特点

主要有两大类：分别是基于哈希表的结构和基于树的结构。
基于哈希表的比如说Redis数据库；MySQL中大部分的存储引擎都是基于树的

---

12.为什么不采用哈希表结构

• 哈希表仅能完成等值查找，如果要进行范围查找，那么查找的时间复杂度就会变成O(n)，而树由于其有序性，仍然保持O(logn)。
• 哈希表存储是没有顺序的，因此如果进行Order By的时候，还需要对结构进行重新排序。
  对于联合索引，哈希表将联合后的索引一起求哈希值，无法单独对一个或几个索引建进行查询。哈希表无法做到最左匹配原则
• 哈希表无法实现模糊查询
• 对于等值查询来说，哈希值的效率非常高，但是如果要查找的列存在大量重复的话，那么效率会降低到O(n)
• InnoDB本身也是支持哈希表的，它提供了自适应哈希表，当某个数据经常被访问，那么他会将数据存储到哈希表中，下次查询时直接从哈希表读取数据。

---

13.B树和B+树的区别

• B树的数据即存储的叶子节点也存储在非叶子节点；B+树的数据都存储的叶子节点，其非叶子节点存储的都是目录项。导致B+树在查找中效率更加稳定，英文查询数据所需磁盘IO次数相同。B树由于非叶子节点也存储数据，因此查找某一条记录所需要的IO次数不固定
• 存储相同的数据通常B+树的层数更少，因此非叶子节点仅仅存储目录项，所以整个树的高低更低，IO次数少，所以效率比B树高
• 在范围查找和排序时，B+树效率更高。因此其叶子节点构成了一个有序链表，查找起来速度很快。B树需要中序遍历才可以。

---

14.B+树的存储能力如何？为何说一般查找行记录，最多只需1~3次磁盘IO

InnoDB存储引擎中页的大小为16KB, 一般表的主键类型为INT (占用4个字节)或BIGINT (占用8个字节)，指针类型也一般为4或8个字节，也就是说一个页(B+Tree 中的一个节点)中大概存储16KB/(8B+8B)=1K个键值(因为是估值，为方便计算，这里的K取值为10^{3。也就是说一个深度为3的B+Tree索引可以维护10}3 * 10^3 * 10^3 = 10亿条记录。(这里假定一个数据页也存储10^3条行记录数据 了)实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree 的高度一般都在2~4层。MySQL 的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要 1~3次磁盘1/0操作。

---

15.什么字段应该建立索引

• 有唯一性要求的字段
• where后面的字段
• gruop by 或者order by后面的字段