MySQL索引设计探究

一 索引的目的

索引的目的，在于提高查询效率，它的本质是，通过不断缩小想要获取的数据范围来筛选出最终想要的结果。与我们查阅图书所用的目录是一个道理：先定位到章，然后定位到该章下的一个小节，然后找到页数。相似的例子还有：查字典，查火车车次，飞机航班等。

数据库也是一样，但显然要复杂的多；不仅有等值查询，还有范围查询(>、

二 索引可能会用的数据结构

如果让我们设计数据结构，来存储索引，那我们该怎么设计呢？任何一种数据结构都不是凭空产生的，一定会有它的背景和使用场景；对于索引来说，我们衡量这种数据结构的好坏标准是什么呢？标准：每次查找数据时把磁盘IO次数控制在一个很小的数量级，最好是常数数量级。为什么呢？因为数据库的数据和索引都是存储在磁盘上的，每次的查找操作就是从磁盘中读取数据，然后再在内存中进行查找操作。数据库实现比较复杂，一方面数据是保存在磁盘上的，另外一方面为了提高性能，每次又可以把部分数据读入内存来计算，

因为我们知道访问磁盘的成本大概是访问内存的十万倍左右，所以简单的搜索树难以满足复杂的应用场景。

2-1 二叉树

下图是一个二叉树：

它的特点是：左边比根节点小，右边比根节点大，并且左右两边都是二叉排序树(二叉树的具体定义，可以查看资料，这里不做详细解释，下面的数据结构也是如此)

缺点是：在一些极端情况下，比如，插入的顺序是有序的话，就会出现退化的情况；退化成链表

2-2 红黑树

它是一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是red或black

特点是：在插入的时候同时调整这棵树，让节点尽可能均分分布，保持平衡

红黑树是平衡树中的一种，它复杂的定义以及繁琐的规则无非就是为了保证树的平衡性。一棵红黑树可以保证平衡性，保持平衡性的目的无非就是降低树的高度，提高搜索效率。

2-3 B树

B树就是多路搜索树，B树的每个节点都可以拥有多余两个孩子节点，M路的B树最多可能拥有M个孩子节点。下图是3路B树

为啥要设计成多路呢？1 进一步降低树的高度； 如果路数越多，树的高度越低，但是不能无限增加路数，那样B树会退化成有序数组

文件系统和数据库的索引都是存在硬盘上的，并且如果数据量大的话，不一定能一次性加载到内存中。这么看的话，使用B树这种数据结构来存储索引，貌似也是可以的。那么问题来了：

三 为什么是B+

3-1 B+树的介绍

为什么要用B+树存储索引？那就得从B+树的特点说起。如下所示是一棵B+树：

B+树是一种平衡查找树(B不代表二叉(Binary)， 而是代表平衡(Balance);

它最主要一个特点：非叶子节点不存储真实的数据，只存储指引搜索方向的数据项(如17、35并不真实存在于数据表中)。在这里，浅蓝色的块我们称之为一个磁盘块，可以看到每个磁盘块包含几个数据项（深蓝色所示）和指针（黄色所示）；

它的查找过程如下：如果要查找数据项29，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO，在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计，通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘块3的P2指针，通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询，总计三次IO。

真实的情况是，3层的b+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高。

它的优缺点如下：

优点：

索引可以降低服务需要扫描的数据量,减少了IO次数

索引可以帮助服务器避免排序和使用临时表

索引可以帮助将随机I/O转为顺序I/O

缺点：

占用额外空间,影响插入速度

3-2 B树 VS B+树

最主要的区别在于：

B树是每个索引节点都会数据存储；

B+树数据都存储在叶子节点上，同时叶子节点之间还加了指针形成链表

业务场景： 使用数据库进行数据查找的时候，一般select查找的数据不止一条，有时候会有很多条检索结果，比如按照id排序后选10条。如果是多条的话，B树需要做局部的中序遍历，可能要跨层访问。而B+树由于所有数据都在叶子结点，不用跨层，同时由于有链表结构，只需要找到首尾，通过链表就能把所有数据取出来了；所以，B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题，正是为了解决这个问题，B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作或者说效率太低