共计 3732 个字符，预计需要花费 10 分钟才能阅读完成。
前言
写数据库，我第一工夫就想到了 MySQL、Oracle、索引、存储过程、查问优化等等。
不晓得大家是不是跟我想得一样，我最想写的是索引，为啥呢？
以下这个面试场景，不晓得大家相熟不相熟：
面试官：数据库有几千万的数据，查问又很慢咱们怎么办？
面试者：加索引。
面试官：那索引有哪些数据类型？索引是怎么样的一种构造？哪些字段又适宜索引呢？B+ 的长处？聚合索引和非聚合索引的区别？为什么说索引会升高插入、删除、批改等保护工作的速度？……..
面试者：面试官怎么出咱们公司门来着😂。
是的大家可能都晓得慢了加索引，那为啥加，在什么字段上加，以及索引的数据结构特点，长处啥的都比拟含糊或者甚至不晓得。
那咱们也不多 BB 了，间接开始这次的面试吧。
注释
我看你简历上写到了相熟 MySQL 数据库以及索引的相干常识，咱们就从索引开始，索引有哪些数据结构？
Hash、B+
大家去设计索引的时候，会发现索引类型是能够抉择的。
为什么哈希表、齐全均衡二叉树、B 树、B+ 树都能够优化查问，为何 Mysql 独独喜爱 B + 树？
我先聊一下 Hash：
大家能够先看一下上面的动图
留神字段值所对应的数组下标是哈希算法随机算进去的，所以可能呈现哈希抵触。
那么对于这样一个索引构造，当初来执行上面的 sql 语句：
select * from sanguo where name=’ 鸡蛋 ’
能够间接对‘鸡蛋’按哈希算法算进去一个数组下标，而后能够间接从数据中取出数据并拿到所对应那一行数据的地址，进而查问那一行数据，那么如果当初执行上面的 sql 语句：
select * from sanguo where name>’ 鸡蛋 ’
则无能为力，因为哈希表的特点就是能够疾速的准确查问，然而不反对范畴查问。
如果做成了索引，那速度也是很慢的，要全副扫描。
问个题外话，那 Hash 表在哪些场景比拟适宜？
等值查问的场景，就只有 KV（Key，Value）的状况，例如 Redis、Memcached 等这些 NoSQL 的中间件。
你说的是无序的 Hash 表，那有没有有序的数据结构？
有序数组，它就比拟优良了呀，它在等值查问的和范畴查问的时候都很 Nice。
那它齐全没有毛病么？
不是的，有序的适宜静态数据，因为如果咱们新增、删除、批改数据的时候就会扭转他的构造。
比方你新增一个，那在你新增的地位前面所有的节点都会后移，老本很高。
那照你这么说他基本就不优良啊，特点也没中央放。
此言差矣，能够用来做动态存储引擎啊，用来保留静态数据，例如你 2019 年的支付宝账单，2019 年的淘宝购物记录等等都是很适合的，都是不会变动的历史数据。
有点货色啊小伙子，那二叉树呢？
二叉树的新增和构造如图：
二叉树的构造我就不在这里多 BB 了，不理解的敌人能够去看看数据结构章节。
二叉树是有序的，所以是反对范畴查问的。
然而他的工夫复杂度是 O(log(N))，为了维持这个工夫复杂度，更新的工夫复杂度也得是 O(log(N))，那就得放弃这棵树是齐全均衡二叉树了。
怎么听你一说，均衡二叉树用来做索引还不错呢？
此言差矣，索引也不只是在内存外面存储的，还是要落盘长久化的，能够看到图中才这么一点数据，如果数据多了，树高会很高，查问的老本就会随着树高的减少而减少。
为了节约老本很多公司的磁盘还是采纳的机械硬盘，这样一次千万级别的查问差不多就要 10 秒了，这谁顶得住啊？
如果用 B 树呢？
同理来看看 B 树的构造：
能够发现同样的元素，B 树的示意要比齐全均衡二叉树要“矮”，起因在于 B 树中的一个节点能够存储多个元素。
B 树其实就曾经是一个不错的数据结构，用来做索引成果还是不错的。
那为啥没用 B 树，而用了 B + 树？
一样先看一下 B 加的构造：
咱们能够发现同样的元素，B+ 树的示意要比 B 树要“胖”，起因在于 B + 树中的非叶子节点会冗余一份在叶子节点中，并且叶子节点之间用指针相连。
那么 B + 树到底有什么劣势呢？
其实很简略，咱们看一下下面的数据结构，最开始的 Hash 不反对范畴查问，二叉树树高很高，只有 B 树跟 B + 有的一比。
B 树一个节点能够存储多个元素，绝对于齐全均衡二叉树整体的树高升高了，磁盘 IO 效率进步了。
而 B + 树是 B 树的升级版，只是把非叶子节点冗余一下，这么做的益处是为了进步范畴查找的效率。
进步了的起因也无非是会有指针指向下一个节点的叶子节点。
小结：到这里能够总结进去，Mysql 选用 B + 树这种数据结构作为索引，能够进步查问索引时的磁盘 IO 效率，并且能够进步范畴查问的效率，并且 B + 树里的元素也是有序的。
那么，一个 B + 树的节点中到底存多少个元素最合适你有理解过么？
额这个这个？卧 * 有点懵逼呀。
过了一会还是没想出，只能诚实交代：这个不是很理解咳咳。
你能够换个角度来思考 B + 树中一个节点到底多大适合？
B+ 树中一个节点为一页或页的倍数最为适合。
为啥？
因为如果一个节点的大小小于 1 页，那么读取这个节点的时候其实也会读出 1 页，造成资源的节约。
如果一个节点的大小大于 1 页，比方 1.2 页，那么读取这个节点的时候会读出 2 页，也会造成资源的节约。
所以为了不造成节约，所以最初把一个节点的大小管制在 1 页、2 页、3 页、4 页等倍数页大小最为适合。
你提到了页的概念，能跟我简略说一下么？
首先 Mysql 的根本存储构造是页(记录都存在页里边)：
各个数据页能够组成一个双向链表
而每个数据页中的记录又能够组成一个单向链表
- 每个数据页都会为存储在它里边儿的记录生成一个页目录，在通过主键查找某条记录的时候能够在页目录中应用二分法疾速定位到对应的槽，而后再遍历该槽对应分组中的记录即可疾速找到指定的记录
以其余列 (非主键) 作为搜寻条件：只能从最小记录开始顺次遍历单链表中的每条记录。
所以说，如果咱们写 select * from user where username=’ 丙丙 ’ 这样没有进行任何优化的 sql 语句，默认会这样做：
定位到记录所在的页
- 须要遍历双向链表，找到所在的页
从所在的页内中查找相应的记录 - 因为不是依据主键查问，只能遍历所在页的单链表了
很显著，在数据量很大的状况下这样查找会很慢！看起来跟回表有点点像。
哦？回表你聊一下。
卧槽，该死，我嘴干嘛。
回表大略就是咱们有个主键为 ID 的索引，和一个一般 name 字段的索引，咱们在一般字段上搜寻：
select * from table where name = ‘ 丙丙 ’
执行的流程是先查问到 name 索引上的“丙丙”，而后找到他的 id 是 2，最初去主键索引，找到 id 为 2 对应的值。
回到主键索引树搜寻的过程，就是回表。不过也有办法防止回表，那就是笼罩索引。
哦？那你再跟我聊一下笼罩索引呗？
！！！我这个嘴。。。
这个其实比拟好了解，方才咱们是 select *，查问所有的，咱们如果只查问 ID 那，其实在 Name 字段的索引上就曾经有了，那就不须要回表了。
笼罩索引能够缩小树的搜寻次数，晋升性能，他也是咱们在理论开发过程中常常用来优化查问效率的伎俩。
很多联结索引的建设，就是为了反对笼罩索引，特定的业务能极大的晋升效率。
索引的最左匹配准则晓得么？
最左匹配准则：
索引能够简略如一个列 (a)，也能够简单如多个列 (a,b,c,d)，即联结索引。
如果是联结索引，那么 key 也由多个列组成，同时，索引只能用于查找 key 是否存在（相等），遇到范畴查问 (>、<、between、like 左匹配)等就不能进一步匹配了，后续进化为线性查找。
因而，列的排列程序决定了可命中索引的列数。
例子：
如有索引 (a,b,c,d)，查问条件 a=1 and b=2 and c>3 and d=4，则会在每个节点顺次命中 a、b、c，无奈命中 d。(c 曾经是范畴查问了，d 必定是排不了序了)
总结
索引在数据库中是一个十分重要的知识点！
上面谈的其实就是索引最根本的货色，N 叉树，跳表、LSM 我都没讲，同时要创立出好的索引要顾及到很多的方面：
最左前缀匹配准则。这是十分重要、十分重要、十分重要（重要的事件说三遍）的准则，MySQL 会始终向右匹配直到遇到范畴查问（>,<,BETWEEN,LIKE）就进行匹配。
尽量抉择区分度高的列作为索引，区分度的公式是 COUNT(DISTINCT col)/COUNT(*)。示意字段不反复的比率，比率越大咱们扫描的记录数就越少。
索引列不能参加计算，尽量放弃列“洁净”。比方，FROM_UNIXTIME(create_time)=’2016-06-06′ 就不能应用索引，起因很简略，B+ 树中存储的都是数据表中的字段值，然而进行检索时，须要把所有元素都利用函数能力比拟，显然这样的代价太大。所以语句要写成：create_time=UNIX_TIMESTAMP(‘2016-06-06’)。
尽可能的扩大索引，不要新建设索引。比方表中曾经有了 a 的索引，当初要加（a,b）的索引，那么只须要批改原来的索引即可。
单个多列组合索引和多个单列索引的检索查问成果不同，因为在执行 SQL 时，MySQL 只能应用一个索引，会从多个单列索引中抉择一个限度最为严格的索引(经斧正，在 MySQL5.0 当前的版本中，有“合并索引”的策略，翻看了《高性能 MySQL 第三版》，书作者认为：还是应该建设起比拟好的索引，而不应该依赖于“合并索引”这么一个策略)。
“合并索引”策略简略来讲，就是应用多个单列索引，而后将这些后果用“union 或者 and”来合并起来