数据库为什么需要索引？我们都知道数据库中的数据是存储在磁盘上的。当我们的程序启动后，就相当于在机器的内存中运行了一个进程。所以当我们的程序要查询数据的时候，就必须要从内存中出来到磁盘中去寻找数据，然后再将数据写回到内存中。但是磁盘的io效率远不如内存，所有数据查找的快慢直接影响程序的效率。数据库索引的主要目的是使用合适的数据结构，可以提高查询数据的效率，减少磁盘io的数量，提高数据查找的速度，而不是愚蠢的全局遍历。为什么索引要用B+Tree数据结构呢？如果单纯想快速查找数据，我们觉得哈希表是最快的。根据key，hash到某个slot，一查就可以找到数据的准确位置。那有多快？.但是，我们在做业务的时候，往往只需要一份数据，需求很少。大多数需求是根据一定的条件查询部分数据。这时候hash显示就不太合适了。再考虑树，比如二叉树，平衡二叉树，红黑树，B树等等，都是二叉查找，找数快，但是不管是平衡二叉树还是优化的红黑树，说到底都是二叉树。当节点太多时，它们的高度会更高。我正在寻找一个数据。如果不是根节点，则寻找下一层。如果没有下一层，我就去下一层。这样做的后果就是我可能要找一个数据好几次，每次都执行一次盘。io，而我们索引的目的是减少磁盘io，这样的设计是不行的。那么我们能不能把高度变矮一点呢？因此，让我们再次考虑B树。首先简单介绍一下B-tree的数据结构：先看B-tree的定义。每个节点最多有m-1个关键字（可以存在的键值对）。根节点可以有至少一个关键字。非根节点至少有m/2个关键字。每个节点中的键按升序排列，每个键的左子树中的所有键都小于它，右子树中的所有键都大于它。所有叶子节点都位于同一层，或者说从根节点到每个叶子节点的长度都相同。每个节点存储索引和数据，即对应的键和值。因此，根节点的关键词数量范围：1<=k<=m-1，非根节点的关键词数量范围：m/2<=k<=m-1。这里的m代表顺序，顺序表示一个节点最多有多少个子节点，所以在描述B树的时候需要指定它的顺序。让我们再举一个例子来说明上面的概念。比如这里有一个5阶的B-tree，根节点的范围：1<=k<=4，非根节点的范围：2<=k<=4接下来我们来解释一下插入通过一个例子介绍B树的插入过程，然后讲解删除关键字的过程。1.2插入B树时，需要记住一个规则：判断当前节点的key个数是否小于等于m-1，如果是，直接插入，如果不是，则替换中间key用这个节点的节点分为左右两部分，中间的节点可以放在父节点中。例子：在一棵5阶B树中，一个节点最多有4个key，最少有2个key（注：以下节点用一个节点来表示key和value）。Insert18,70,50,40为什么Mysql使用B+Tree作为索引插入22？为什么Mysql使用B+Tree作为索引插入22？发现这个节点的key大于4，所以需要拆分。规则上面已经说了，拆分之后，如下。为什么Mysql使用B+Tree作为索引，然后插入23,25,39为什么Mysql使用B+Tree作为索引进行拆分，得到如下。为什么Mysql要用B+Tree做索引，所以B-tree每一层的节点数会增加。同样的数据量，B-tree的高度会比二叉树低，需要的ios数量也会减少，所以符合我们的索引需求。那为什么MySQL最终选择了B+树呢？比B树好在哪里？我们先来看看B+树和B树的区别：B+树的叶子节点包含了这棵树的所有键值，非叶子节点不存储数据，只存储索引，所有数据都存储在叶子节点中。B树是每个节点都有索引和数据。B+树的每个叶子结点都存储着相邻叶子结点的指针，叶子结点本身按照key的大小依次链接起来。如图：为什么Mysql要用B+Tree做索引？第一点：当非叶子节点只存储索引键不存储数据时，可以减少非叶子节点占用的空间，同样容量的节点可以存储更多的索引，如果索引很多，也是一个三-一层B+树，阶数会增加，比B树存储更多的数据。第二点：B+树叶子节点存放的是相邻叶子节点的指针。要了解这个指针的好处，我们首先要知道，从磁盘读取数据时，往往不是严格按需读取，而是每次都会预读。即使只需要一个字节，磁盘也会从这个位置开始，依次向后读取一定长度的数据到内存中。其理论依据是计算机科学中众所周知的局部性原则：当使用一条数据时，通常会立即使用附近的数据。程序运行过程中需要的数据通常比较集中。预读的长度一般是页的整数倍。它也是计算机管理内存的一个逻辑块。硬件和操作系统常常将主存和磁盘存储区划分为大小相等的连续块。每个存储块称为页（在许多操作系统中，页大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发缺页异常。这时，系统会向磁盘发送一个读信号，磁盘会找到数据的起始位置，并不断地向后读取一页或几页。载入内存，然后异常返回，程序继续运行。现在看看B+树的叶子节点的指针，就可以明白它的用处了。在预读时，可以保证顺序读取的数据是有序的。可能有同学提到过B*树，它是在B+树的基础上，增加了非叶子节点的链表指针。个人觉得B型树没什么用，因为我觉得没必要。我们不在非叶子节点中存储数据，数据都在叶子节点中。链表指针不能用于非叶节点。一些花里胡哨的概念聚簇索引和非聚簇索引：上面我们提到了B+树的叶子节点存放的是索引键的数据数据，但是不同的mysql引擎对于存放数据的选择是不同的。MyISAM结合了索引文件和真实数据文件存储在两个文件中。索引文件中存储的数据是索引键对应的数据在数据文件中的地址值，而InnoDB将正式数据存储在叶子节点中。所以聚类和非聚类就是区分叶子节点存储的数据是否真实（可以理解为叶子节点是否拥挤？）回表：回表也简单，但是必须先了解主键索引和普通索引。叶子节点存储的是真正的数据，只存储在主键索引中，普通索引中存储的数据是主键索引的key。然后我们可以更好地理解它。比如我为一张表的name字段建了一个普通的索引。我想从name='test'的表中选择*。这时候我们在找到测试节点的时候，得到的key只是这一行数据对应的主键，如果我们要获取整行的数据，就只能拿着这个key去主键索引树中重新找了。此操作称为返回表。最左匹配原则：当我们创建一个新的复合索引，比如(name+age)，使用wherename=xxandage=xx查询时，会使用复合索引，而whereage=xxandname=xx则不会走。这是因为MySQL创建联合索引的规则是先对联合索引最左边的第一个字段进行排序，根据第一个字段的排序，然后对第二个字段进行排序。如果这篇文章对你有帮助，别忘了连打3个，点赞、转发、评论，我们下期再见！了解更多JAVA知识和技能，关注和私信博主(666)
