Mysql索引的B+树结构

B树

B树是一种自平衡多路搜索树。每个节点可以包含多个关键字和指针（关键字就是整行业务数据），因此B树的每个节点都会存储数据，这样有利于支持随机访问。且B树节点之间是没有指针相连的。

B+树

B+树是由多个页组成的多层级结构，本质是一种多路搜索树。B+树与B树不同的地方在于B树是每个节点都存储数据，而B+树非页子节点只存储索引信息和指向页子节点的指针。另外B+树的页子节点是通过指针连接起来的，支持顺序访问和范围访问。

因为索引要比存储数据要小得多，所以B+树相比于B树也能存储更多的数据。

1. B+树是一种多路搜索树，即每个节点可以包含多个子节点。这意味着每个节点可以存储多个关键字和对应的指针，使得B+树可以高效地存储大量的数据。
2. B+树具有平衡性，能够保持平衡，即任何时刻，从根节点到叶子节点的路径长度相等，一般来说只差一个层级。这保证了在查找、插入和删除等操作时，树的高度始终保持在较小的范围内，保持了高效的查找性能。
3. B+树具有顺序性，该树的页子节点形成了一个有序链表，叶子节点之间通过指针连接起来（也就是末级的页子节点都顺序链接成了一个有序链表）。这种有序性使得范围查询操作变得更加高效，可以通过遍历叶子节点的有序链表来获取范围内的数据。同时这种有序性在连续的查询数据中，B+树能利用磁盘预读的特性提高数据的顺序访问性能，减少磁盘IO操作的次数，更少的磁盘IO操作也就意味着更高效的性能。
4. B+树的非叶子节点仅存储索引信息，而实际的数据存储在叶子节点中。这样的设计使得B+树的高度相对较小，提高了查找效率，并且减少了非叶子节点的存储空间开销。当然不仅B+树的高度小了，相比于B树，每个节点能存储更多的索引，也就意味着能通过这些索引找到更多的数据，在大范围搜索数据的时候，当数据在一个节点索引的所有数据找不到的时候，就可以过滤掉大量数据，能够有效的减少磁盘IO操作次数，提高数据访问效率（相当于筛茶叶，一次IO就能筛一大包，别的都是一次筛一小包，要多次IO）。
5. B+树适用适用于外存储结构，由于B+树的特性，特别是有序的叶子节点链表和非叶子节点的索引存储，使得它非常适合于外存储结构，如数据库索引和文件系统索引等。B+树索引的内部节点只包含键值，相对于B树来说紧凑，也更节省内存空间。

末级的页子节点放行数据；非页子结点放索引信息，即组件ID和页号，用于加速查询。页子节点的数据页并非顺序遍历查找数据，而是通过内部的页目录信息，进行二分查找的方式进行对应数据查找（O(N) → O(logN)）

通过索引信息找到对应页，再将页内所要的数据从磁盘通过IO加载到内存中。

综上可以看出，B+树通过创建多个页表的方式，采用空间换取时间加快了查询速度。

跳表

相比于B+树，跳表是在基本顺序链表的基础上，再生成一层或一层以上的链表进行链接跳跃。通过多层链表的方式，快速知道数据大概在什么位置，跳跃到范围内进行查找。

综上也可以看出，跳表实际上也是采取空间换取时间的做法。

对比一下B+树与跳表

B+树

B+树和跳表都适用于范围查询，都是用来提高搜索性能的。但是在插入和删除数据时，由于B+树本身是平衡多路搜索树的原因，导致它每插入一个数据时，为了维持B+树的平衡性，B+树会不断进行数据页的调整。这时候分三种情况：①页子节点和索引节点（非页子节点）都没满。②页子节点满了，索引节点没满。③页子节点和索引节点都满了。

①页子节点和索引节点都没满

这种情况直接将新插入的数据插入到任意一个页子节点就行。

②页子节点满了，索引节点没满

这种情况需要拆分一个页子节点作为分裂出来的新页子节点，将新插入的数据插入到分裂出来的页子节点中，同时对应的索引节点要新增索引信息。

③页子节点和索引节点都满了

这种情况对应的页子节点和索引节点都要进行拆分作为分裂的两个新节点，将新插入的数据插入到分裂出来的页子节点中，同时对应的索引节点要新增索引信息，索引节点要被新分裂的索引节点作为索引数据去新增索引信息。

从上面可以看出只有在情况③中B+树才会新增节点。

跳表

但是跳表不一样，跳表新插入一个数据时，最低层的链表是要插入新数据的，但其他几层要不要插入这个数据作为索引我们是不知道的，因为这个操作靠的是纯随机函数。

理论上要达到跳表的二分效果，上层节点数要是下层的二分之一，例如第一层是全部数据即为1，那么第二层就得是二分之一，第三层就得是二分之一的二分之一，以此类推。

那么我们从上面就可以看出纯随机这个问题，新插入的这个数据在哪一层就是纯随机的。当数据量够大时，就符合理想的二分效果。但这也就意味着小数据量插入时是不看插入位置的附近位置情况的。

那么问题回到Mysql索引为什么使用B+树而不使用跳表？

针对读操作来说：

因为B+树是一个多叉树结构，每个节点都是一个数据页，能存放许多数据信息，所以扇出很高，每个索引页都能指向几乎上千个子页，三层左右就能存储2000万左右的数据。那么要想查询这些数据，最多需要三次磁盘IO操作。

而跳表是顺序链表结构，一个数据即是一个节点。如果最底层要存放2000万个数据，且每次都需要达到二分查找的效果，2000万个数据大约需要24层的跳表去存储。那如果在最坏的情况下，这24层数据得分布在不同的数据页里，这就意味着查一次数据得进行24次磁盘IO操作。

因此上述可以看出，存放同一量级的数据，跳表的高度明显要比B+树高很多，这就意味着B+树查询的速度比跳表要快不少。

针对写操作来说：

B+树如上面对比的时候可以知道，会有需要将索引页和数据页拆分的情况，三种情况都要维持好B+树的平衡性。跳表则不需要维持平衡性，只需要使用随机函数进行选出插入的层数，没有旋转和维持的开销。所以跳表写入的性能要比B+树好。

但实际数据库应用情况我们都知道写操作远远比读操作要少得多。因此Mysql选择了对于读操作性能更好的B+树作为索引的底层。

题外话，我们了解过 Redis 后会知道他的Hset使用的是跳表，那有人可能会想为什么 Redis 也是数据库却要用跳表作为底层？

有个重要的点就是 Redis 是内存级的数据库，它读写的数据都缓存在内存中。当应用程序想要调用 Redis 里有的数据时，应用程序是可以通过系统调用直接从内存里获取的，不需要有磁盘IO操作。

我们学过数据库系统这门理论都会明白，实际上最拖数据库查询后腿的并不是什么代码问题，而是实实在在的物理层面上的问题，磁盘IO虽然一步步在优化，但在如今那物理上的时间延迟仍然在这种微秒为量级都算慢的层面上会造成很大的性能问题。

在内存级数据库中，数据的存取速度受限于 CPU 和内存的速度，而不像磁盘IO操作那样受限于磁盘的读写速度，且跳表具有较好的查找和插入性能，在内存中进行操作时速度非常快。因此，选择跳表作为底层实现可以更好地满足 Redis 对于高速读写操作的需求，从而提供更好的性能和响应速度。

后日谈：

Mysql 本身的底层其实也用的是B+树的变种，末级的页子节点并不只是单向链表，而是双向的，提高了数据查询的效率。

跳表虽然在每个节点上的存储开销可能较小，但是需要维护多级索引，可能会占用较多的额外内存空间。B+树节点通常较大，存储的键值对较多，能够有效利用内存。这也是为什么 Mysql 后面用B+树作为底层实现的原因之一。