索引
1、没有索引如何查找数据？
在一个页中的查找，分为两种情况：
- 以主键为搜索条件
可以在 页目录 中使用二分法快速定位到对应的槽，然后再遍历该槽对应 分组中的记录即可快速找到指定的记录。
- 以其他列作为搜索条件
对非主键列的查找的过程可就不这么幸运了，因为在数据页中并没有对非主键列建立所谓的 页目录 ，所以 我们无法通过二分法快速定位相应的 槽 。这种情况下只能从 最小记录 开始依次遍历单链表中的每条记录， 然后对比每条记录是不是符合搜索条件。很显然，这种查找的效率是非常低的。
在很多页中的查找，可以分为两个步骤：
- 定位到记录所在的页。
- 从所在的页内中查找相应的记录。
在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，在每一个页中根据我们刚刚唠叨过的查找方式去查找指定的记录。
2、索引是什么？
索引本质是排好序的数据结构，一种特殊的文件，包含着对数据表里所有记录的引用指针，直接在索引中查找符合条件的选项，加快数据库的查询速度，而不是一行一行去遍历数据后才选择出符合条件的。
优点：
- 可以大大加快数据的检索速度，这也是创建索引的最主要的原因。
- 通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。
缺点：
- 索引是一个文件，它是要占据物理空间的。
- 创建索引和维护索引要耗费时间，具体地，当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，会降低增/改/删的执行效率。
3、MySQL有哪几种索引类型？
- 从数据结构上来划分：哈希索引，B树索引，B+树索引。
- 从功能层次上来划分：普通索引，唯一索引，主键索引，联合索引。
- 普通索引：即一个索引只包含单个列，一个表可以有多个单列索引。
- 唯一索引：索引列的值必须唯一，但允许有空值。
- 主键索引：一种特殊的唯一索引，不允许有空值，一般在建表时同时创建主键索引;
- 联合索引：多列值组成一个索引，专门用于组合搜索。
- 从物理存贮上来划分：聚簇索引，非聚簇索引。
4、聚簇索引和非聚簇索引？⚡
聚簇索引： 聚簇索引是按照每张表的主键构造一颗B+树，叶子节点中存放的就是整张表的数据，将聚簇索引的叶子节点称为数据页。
c1，c2，c3三列，我们以c1列建立索引，索引树如下图所示：
聚簇索引的特点：
聚簇索引不需要我们显式去创建，InnoDB 存储引擎会自动的为我们创建聚簇索引，并且在 InnoDB 存储引擎中， 聚簇索引 就是数据的存储方式（所有的用户记录都存储在了叶子节点 ），也就是所谓的索引即数据，数据即索引。
聚簇索引的优点：
- 数据访问更快，聚簇索引将索引和数据保存在同一个 B+ 树中，因此从聚簇索引中获取数据比非聚簇索引更快；
- 聚簇索引对于主键的排序查找和范围查找速度非常快。
聚簇索引的缺点：
- 插入速度严重依赖于插入顺序，按照主键的顺序（递增）插入是最快的方式，否则将会出现页分裂，严重影响性能。
- 更新主键的代价很高，将会导致被更新的行移动，所以对于 InnoDB 表，一般定义主键为不可更新。
- 聚簇索引只能在搜索条件是主键值时才能发挥作用，因为 B+ 树中的数据都是按照主键进行排序的。
非聚簇索引：非聚簇索引叶子节点存储的是主键值，而不是数据的物理地址，所以访问数据需要二次查找，推荐使用覆盖索引，可以减少回表查询。
以c2列作为索引列，建立B+树：
非聚簇索引的特点：
- B+ 树的叶子节点存储的并不是完整的用户记录，而只是 索引列+主键 这两个列的值。
- 以索引列大小排序的 B+ 树只能确定我们要查找记录的主键值，所以如果我们想根据 c2 列的值查找到完整的用户记录的话，仍然需要到 聚簇索引 中再查一遍，这个过程也被称为 回表。
非聚簇索引的优点：
- 非聚簇索引由于不存储实际数据，所以实际文件较小，相比于聚簇索引再读取时可以减少磁盘IO。
- 非聚簇索引使用主键作为”指针” 而不是使用地址值作为指针的好处是，减少了当出现行移动或者数据页分裂时辅助索引的维护工作。
非聚簇索引的缺点：
- 需要进行回表查询，即查询到对应的聚簇索引之后再通过聚簇索引查询到所需数据。
5、索引底层实现（数据结构）？ ⚡
- Hash索引
- 哈希表是一种以键—值（key-value）存储数据的结构，我们只要输入待查找的值即 key，就可以找到其对应的值即 Value。哈希的思路很简单，把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。
- 不可避免地，多个 key 值经过哈希函数的换算，会出现同一个值的情况。处理这种情况的一种方法是，拉出一个链表。
- 哈希表这种结构适用于只有等值查询的场景，比如 Memcached 及其他一些 NoSQL 引擎。
- B 树索引
- B 树索引，又称平衡树索引，B Tree能加快数据的访问速度，因为存储引擎不再需要进行全表扫描来获取数据，数据分布在各个节点之中。
- 一棵 m 阶 B Tree 的特性如下：
- 每个结点最多 m 个子结点；
- 所有的叶子结点都位于同一层；
- 每个节点中的元素按关键字key从小到大排列；
- 每个元素子左结点的值都小于或等于该元素，右结点的值都大于或等于该元素。
- 数据库以 B-Tree 的数据结构存储数据的图示如下：
- B+Tree索引
- 是B-Tree的改进版本，同时也是数据库索引所采用的存储结构。数据都在叶子节点上，并且增加了顺序访问指针，每个叶子节点都指向相邻的叶子节点的地址。相比B-Tree来说，进行范围查找时只需要查找两个节点，进行遍历即可。而B-Tree需要获取所有节点，相比之下B+Tree效率更高。
- B+tree性质：
- n棵子树的节点包含n个关键字，不用来保存数据而是保存数据的索引。
- 所有的非叶子结点只存储 关键字key信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接；
- 所有具体数据都存在叶子结点中；
- 所有的叶子结点中包含了全部元素的信息；
- 所有叶子节点之间都有一个链指针。
- 数据库以 B+ Tree 的数据结构存储数据的图示如下：
6、为什么索引结构默认使用B+Tree，而不是B-Tree，Hash，二叉树，红黑树？
B+树与B树相比：
- B+树的磁盘读写代价更低：B+树的非叶子节点不存贮数据，只存贮关键词key信息，进行数据索引，使每个非叶子节点所能保存的关键字大大增加。这样磁盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。
- 更加适合区间查询：B树的数据分布在各个节点之中，当进行范围查找时会出现回旋查找。而B+树的数据都存储在叶子结点中，并且MySQL 索引数据结构对经典的 B+Tree 进行了优化，增加一个指向相邻叶子节点的链表指针，就形成了带有顺序指针的 B+Tree，提高了区间访问的性能，防止回旋查找。
B+树与Hash相比：
- Hash虽然可以快速定位，但是没有顺序，IO复杂度高。
- Hash索引基于Hash表实现，只有Memory存储引擎显式支持哈希索引 。
- Hash索引因为不是按照索引值顺序存储的，就不能像B+Tree索引一样利用索引完成排序。
- 如果有大量重复键值得情况下，哈希索引的效率会很低，因为存在哈希碰撞问题 。
B+树与红黑树相比：
- 红黑树的高度随着数据量增加而增加，IO代价高。
B+树与普通二叉树相比：
- 树的高度不均匀，不能自平衡，查找效率跟数据有关（树的高度），并且IO代价高。
- 普通二叉树存在退化的情况，如果它退化成链表，相当于全表扫描。
B+树与平衡二叉树相比：
- 读取数据的时候，是从磁盘读到内存。如果树这种数据结构作为索引，那每查找⼀次数据就需要从磁盘中读取⼀个节点，也就是⼀个磁盘块，但是平衡二叉树的每个节点只存储⼀个键值和数据，树的节点将会非常多，高度也会极其高。如果是 B+ 树，可以存储更多的节点数据，树的高度也会降低，因此读取磁盘的次数就降下来了，查询效率就会更快。
7、索引的B+树到底有多高？
InnoDB中页的大小一般为16 KB，我们假设一行记录的数据大小为1KB（实际上现在很多互联网业务数据记录大小通常就是1K左右）
- 如果 B+ 树只有1层，也就是只有1个用于存放用户记录的节点，可以存放 16KB / 1KB = 16条数据记录；
- 如果 B+ 树有2层：
- 我们假设主键ID为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节，这样一共14字节，一个页中共可以存放 16 * 1024 / 14 = 1170个指针，因此可以存放 1170 * 16 = 18720条数据记录；
- 如果 B+ 树有3层：可以存放 1170 * 1170 * 16 = 21902400，大约2000w条数据记录。
所以在InnoDB中B+树高度一般为1-3层，它就能满足千万级的数据存储。在查找数据时一次页的查找代表一次IO，所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。
与此同时，我们也可以发现索引的B+树高度也跟索引字段的数据类型有关，数据类型越小，索引占用的存储空间就越少，在一个数据页内就可以放下更多的记录，从而减少磁盘 I/O 带来的性能损耗，也就意味着可以把更多的数据页缓存在内存中，从而加快读写效率。
8、索引的代价(索引是不是越多越好)？
- 空间上的代价
- 每建立一个索引都要为它建立一棵 B+ 树，每一棵 B+ 树的每一个节点都是一个数据页， 一个页默认会占用 16KB 的存储空间，一棵很大的 B+ 树由许多数据页组成，就是很大的一片存储空间，在增删改记录的时候性能就越差。
- 时间上的代价
- 每次对表中的数据进行增、删、改操作时，都需要去修改各个 B+ 树索引。而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行一些记录移位，页面分裂、页面回收啥的操作来维护好节点和记录的排序。
