问题1、数据库为什么要设计索引？图书馆藏书1000万册。如果你想从他们那里找到《架构师之路》，你可以一一搜索。你什么时候去找他们？于是，馆员设计了一套规则：（1）一层是历史，二层是文学，三层是IT……（2）IT，分为软件和硬件……（3)软件类别，并按标题字母顺序排序...快速找到一本书。以此类推，数据库存储了1000万条数据。要从中找出name=”shenjian”的记录，一条一条查看。你想什么时候检查它们？因此，必须有一个索引来提高数据库的查找速度。问题2.哈希（hash）比树（tree）快，为什么索引结构要设计成树？加快查找速度的常见数据结构有两种：（1）哈希，如HashMap，查询/插入/修改/删除的平均时间复杂度为O(1)；(2)树，如平衡二叉树，查找树，查询/插入/修改/删除的平均时间复杂度为O(lg(n))；可以看出无论是读请求还是写请求，hash类型的索引都比tree类型的索引速度快，那么为什么要把索引结构设计成树呢？画外音：80%的同学答不上面试中的问题。索引设计成树形，这与SQL的要求有关。对于这样一个单行查询的SQL需求：select*fromtwherename="shenjian";事实上，哈希索引更快，因为每次只查询一条记录。画外音：因此，如果业务需求是单行访问，比如护照，确实可以使用哈希索引。但是对于排序查询的SQL需求：分组：groupbysorting：orderbycomparison：<,>...hash类型的索引，时间复杂度会退化为O(n)，树的“有序”特性类型依然可以保持O(log(n))的高效率。任何偏离要求的设计都是耍流氓。还有一件事，InnoDB不支持哈希索引。问题三、为什么数据库索引要用B+树？为了保持知识体系的完整性，简单介绍几种树。第一种：二叉搜索树二叉搜索树，如上图所示，是最为人熟知的数据结构，这里就不做介绍了。为什么它不适合用作数据库索引？(1)数据量大时，树的高度会比较高，数据量大时，查询会变慢；(2)每个节点只存储一条记录，可能导致一次查询多次磁盘IO；画外音：这棵树经常出现在大学教科书里，所以最为人熟知。第二种：B-treeB-tree，如上图所示，它的特点是：（1）不再是二分查找，而是m-fork查找；(2)叶子节点和非叶子节点都存储数据；(3)中序遍历，可以得到所有节点；画外音，我真的不想介绍这个特性：非根节点j包含的关键字个数满足，(┌m/2┐)-1<=j<=m-1，节点分裂时满足这种情况。B-tree作为实现索引的数据结构被创建，因为它可以完美地利用“局部性原理”。什么是局部性原则？局部性原理的逻辑如下：（1）内存读写块，磁盘读写慢，而且慢得多；(2)磁盘预读：磁盘读写不是按需读，而是按页预读。一次读取一页数据，每次加载更多数据。如果以后要读取的数据在这个页中，就可以避免以后的磁盘IO，提高效率。画外音：通常，一页数据是4K。(3)局部性原则：软件设计应尽量遵循“数据读取集中”和“使用一条数据，大概率会使用附近的数据”，这样磁盘预读可以充分提高磁盘IO；为什么B-tree适合做索引？(1)由于是m叉形，高度可以大大降低；(2)每个节点可以存储j条记录。如果节点大小设置为页面大小，比如4K，可以充分利用预读特性，大大减少磁盘IO；第三种：B+树B+树，如上图所示，仍然是一个m-fork搜索树。在B树的基础上，做了一些改进：（1）非叶子节点不再存储数据，数据只存储在同层的叶子节点上；画外音：B+树中从根到每个节点的路径长度是一样的，但是B树不是这样的。(2)叶子之间增加链表获取所有节点，不再需要中序遍历；这些改进使得B+树比B树具有更好的特性：（1）范围搜索，在定位到min和max之后，中间的叶子结点就是结果集，不需要中序回溯；画外音：范围查询在SQL中用的比较多，这是B+树相对于B树最大的优势。(2)叶子节点存储实际的记录行，比较紧凑，适合大数据量的磁盘存储；非叶子节点存储记录的PK，用于查询加速，适合内存存储；(3)非叶子节点，不存储实际的记录，而只存储记录的KEY，那么在内存相同的情况下，B+树可以存储更多的索引；最后，量化为什么m-forkB+树的高度比二叉搜索树的高度低很多？粗略计算一下：(1)局部性原则，设一个节点的大小为一页，每页4K，假设一个KEY有8个字节，一个节点可以存放500个KEY，即j=500(2)m个forkTree，大约m/2<=j<=m，也就是差不多可以有1000个forktree(3)那么：一级树：1个节点，1*500个KEY，大小4K二级树：1000个节点，1000500=50W个KEY，大小10004K=4M三层树：10001000个节点，10001000500=5亿个KEY，大小10001000*4K=4G画外音：嗯，大家帮我看看有没有算错。可以看出，存储大量数据（5亿）不需要很高的树深（高度3），索引也不会占用太多内存（4G）。总结数据库索引用于加速查询。虽然哈希索引是O(1)，树索引是O(log(n))，但是SQL有很多“有序”的要求，所以数据库使用树索引。InnoDB不支持哈希索引。数据预读的思路是：磁盘读写不是按需读，而是逐页预读，一次读一页数据，每次加载更多的数据时间，以减少以后的磁盘IO局部性原则：软件设计应该尽量遵循“数据读取集中”和“使用一块数据，大概率使用附近的数据”，使得磁盘预读可以充分提高磁盘IO数据库索引最常用的B+树：(1)非常适合磁盘存储，可以充分利用局部性原理，磁盘预读；(2)树高极低，可储存大量数据；(3)索引本身占用的内存很小；(4)可以很好地支持单点查询、范围查询、有序查询；
