为什么要有索引？索引的作用是什么？
索引的出现其实就是为了提高数据查询的效率，就像书的目录一样。一本书我们可以通过目录中快速的定位其中的某一个知识点；对于数据库而言索引其实就是它的目录，可以通过索引快速的定位都某一条或多条记录。
哈希表是一个以 键-值（key-value） 存储数据的结构，我们只要输入待查找的值即 key，就可以找到对应的值即 value。
把值放在数组里，用一个哈希函数把 key 转换成一个确定的位置，然后把 value 放在数组的这个位置。当多个 key 值经过哈希函数的换算会出现同一个值的情况。这时候会拉出一个链表进行存储。
假设现在维护一个身份证信息和姓名的表，表示根据身份证查找对应的名字，这时对应的哈希索引示意图如下
图 1 哈希表示意图
图中，User2 和 User4 根据身份证号算出来的值都是 N，所以后边跟了一个链表存储。如果要找到 User2 对应的名字是什么，首先通过哈希函数计算出 ID_card_n2 的值为 N，然后按顺序遍历找到 User2。
在这里四个 ID_card_n 的值并不是递增的，这样做的好处就是增加的时候会很快，直接往后边追加；缺点是数据的存储并不是有序的，所以在做区间查询时会进行全表扫描，速度会非常慢。
哈希表这个结构只适用于等值查询。
将数据存放到数组中，数据在数组中是按顺序存储的，从左到右依次从大到小或从小到大。
以哈希表中的例子，使用有序数组实现的结果如下
图 2 有序数组示意图
这里假设身份证是没有重复的，这个数组是按照身份证的递增顺序保存的。这时候如果刷要查询 ID_card_n2 对应的姓名，用二分查找法可以快速定位到这条记录，同时如果要进行范围查询也是很快的，比如要查找身份证号在 [ID_card_X, ID_card_N] 区间的 User，可以先用二分查找法找到 ID_card_X 的值，如果没有则找到大于 ID_card_X 的第一个值，然后向右遍历，知道找到第一个大于 ID_card_N 的值退出循环。
但是往数组中插入一条记录的时候需要挪动后边所有的元素，这样的成本太高，同样的删除一条记录也会导致后边所有的元素往前挪动。
有序数组结构适用于等值和范围查询，但是插入和删除的效率太慢。
二叉搜索树每个节点大于左儿子小于右儿子。
上文例子，二叉搜索树实现如下
如果我们要找到 ID_card_n2 的话，根据二叉搜索树的特点，按照图中的搜索顺序依次是：UserA→UserC→UserF→User2。
InnoDB 使用了 B+ 树索引模型，数据都是存储在 B+ 树中的，每一个索引都对应一棵 B+ 树。
B树 是一棵多路平衡树且有以下特点：
B+ Tree 是在 B-Tree 基础上的优化，使其更适合实现外存储索引结构，InnoDB引擎就是基于它实现索引结构，B+Tree 相对于 B-Tree 的优势：
B+树 为了维护索引的有序性，在插入新值的时候需要做必要的维护，如果插入新的行 ID 值为 700，则只需要在 R5 的记录后插入一个新的将是。如果插入值的 ID 为400，需要逻辑上挪动后面的数据，空出位置。
如果 R5 所在的数据页已经满了，根据 B+树 的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去，这个过程称为页分裂。页分裂还会影响数据页的利用率，原本在一个页的数据，现在分到两个页中，整体的空间利用率降低大约 50%。
当相邻的两个页由于删除了数据，利用率很低之后，会将数据页做合并，合并的过程可以认为是分裂过程的逆过程。
对于以下这两个重建索引的作法，说出你的理解。如果有不合适的，为什么，更好的方法是什么？
为什么重建索引？
索引可能因为删除，或者页分裂等原因，导致数据页有空洞，重建索引的过程会创建一个新的索引，把数据按顺序插入，这样页面的利用率最高，也就是索引更紧凑、更省空间。
解答
重建主键的过程不合理：
主键索引叶子节点中存储的是整行数据，从物理结构的角度也叫 聚簇索引。
聚簇索引最大限度的提高了 IO 密集型应用的性能，但它也有限制：
插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的，否则会出现页分裂，严重影响性能。所以一般 InnoDB 表，都会定义一个自增的id作为主键。
更新主键的代价很高，因为将会导致被更新的行移动。因此，InnoDB表一般主键不可更新。
MySQL默认情况下，主键是允许更新的。MongoDB主键是不允许更新的。
二级索引访问需要回表。
有种情况无需二次查找，就是索引覆盖。
主键ID建议使用整型。因为，每个主键索引的 B+Tree 节点的键值可以存储更多主键ID，每个非主键索引的 B+Tree 节点的数据可以存储更多的主键ID。
如果执行的语句是 select ID from T where k between 3 and 5; ，这时只需要查 ID 的值，而ID的值已经在 k 索引树上了，因此可以直接拿到查询结果，不需要回表。也就是说索引 k 已经覆盖了我们的查询需求，我们称为覆盖索引。
覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。
一个市民信息表上，是否有必要将身份证号 和 名字 建立联合索引？
如果有一个高配请求，要根据市民的身份照查询他的姓名，这个联合索引就很有意义了。它可以在这个高配请求上用到覆盖索引，不需要回表。
现在有这么一个联合索引，（name,age）。
索引项是按照索引定义里面出现的字段顺序排序的，不只是索引的全部定义，只要满足最左前缀，就可以利用索引来加速检索。
既然主键包含了a、b这两个字段，那意味着单独在字段c上创建一个索引，就已经包含三个字段了，为什么要创建“ca”、“cb”这两个索引？
同事告诉他，是因为他们的业务里面有这样的两种语句：
问题，这位同事解释的对吗，为了这两个查询模式，这两个索引是否都是必须的？为什么？
此处还是以市民表的联合索引 (name, age) 为例，需求为 检索出表中 名字第一个字是张，而且年龄是 10岁的所有男孩。
根据最左前缀原则，这个语句在搜索索引树的时候，只能用 “张”，找到一个满足条件的记录 ID3。然后判断其他条件是否满足条件。
在 MySQL5.6 之前，只能从 ID3 开始一个个的回表，到主键索引上找出数据行，在对比字段。
在 MyQL5.6 之后引入了索引下推优化（index condition pushdown），可以在索引遍历的过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，从而减少了回表的次数。
MyISAM 引擎同 InnoDB 一样，都是使用 B+Tree 作为索引结构。差别在于：
上图分别为主索引和辅助索引，由于 MyISAM 的索引文件中仅保存了数据的地址，所以在 MyISAM 中主索引和辅助索引在结构上没有本质的区别，只是主索引要求 key 的唯一性，而辅助索引的 key 是可以重复的。
由于 MyISAM 的 data 域中保存的是数据记录的地址，所以 MyISAM 索引检索的算法为首先按照 B+Tree 搜索算法搜索索引，如果指定的 key 存在，则取出 data 域的值，然后以 data 域的值为地址，读取相应的数据记录。
MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。
事务处理上
MyISAM：强调的是性能，查询的速度比 InnoDB 类型更快，但是不提供事务支持。
InnoDB：提供事务支持。
外键
MyISAM：不支持外键。
InnoDB：支持外键。
MyISAM：只支持表级锁。
InnoDB：支持行级锁和表级锁，默认是行级锁，行锁大幅度提高了多用户并发操作的性能。InnoDB 比较适合于插入和更新操作比较多的情况，而 MyISAM 则适用于频繁的查询的情况。另外， InnoDB 表的行锁也不是绝对的，如果在执行一个 SQL 语句时， MySQL 不能确定要扫描的范围，InnoDB 表同样会锁全表，例如： update table set num=1 where name like '%aaa%'; 。
全文检索
MyISAM：支持全文检索。
InnoDB：不支持全文检索。
表主键
MyISAM：允许没有主键的表存在。
InnoDB：如果没有主键，则会自动生成一个 6 字节的主键（用户不可见）。
表的具体行数
MyISAM： select count(*) from table ，MyISAM 只要简单的读出保存好的行数。因为 MyISAM 内置了一个计数器， count(*) 时它直接从计数器中读。
InnoDB：不保存表的具体行数，也就是说，执行 select count(*) from table 的时候，InnoDB 要扫描一遍整表来计算有多少行。