mysql索引有点像跳表

因为都是查表。

mysql的索引功能与跳表的形式很像，都是需要从头往下开始查表索引的功能本质上也就是从表格搜索。

跳表是用于有序元素序列快速搜索查找的一个数据结构，很高级也很好用。

B+树、索引、按区间索引

在这里，我们主要复盘 B+ 树的诞生过程，已经了解 B+树 这种数据结构

在MySQL中，有两种语句非常常见：

这两个需求可以用 B+树 完美解决，但是在这之前，我们要先看一看其它数据结构能否满足它：

实际上，跳表的诞生很可能参考了 B+树 ，所以在这里，我们复盘 B+树 诞生的整个过程，让你对 B+树 有一个更深刻的理解。

参照跳表，我们发现， 实现区间查找的最好方式就是在一个有序链表中找到第一个在区间内的值，然后依次输出有序数据，直到超出区间范围 。

但是这样的结构会带来问题，那就是二叉树的索引节点过多， 索引节点的数量相当于数据的数量，这样会造成非常大的内存浪费。

为了解决内存浪费的情况，我们需要将二叉树的索引放到硬盘中，这样可以解决它耗费内存的问题。注意，是索引，也就是保存数据的叶子节点依然在内存中。

但是这会带来新的问题：硬盘的访问速度非常慢，它比内存慢上万倍，这该怎么办呢？

你会发现，使用二叉树查找值需要访问硬盘的次数和树的高度相同，所以如果我们想提高查找效率，可以通过 降低树的高度 实现。

你会发现，这样的结构会显著减小查找次数，从而提高数据的查找效率。那么，这个 m 叉树中的 m ，到底应该是多少呢？

我们知道，大多数 *** 作系统都是使用 段页式方式 将文件读入内存，也就是说，计算机一次最多读取 一页 大小的数据，一旦超过这个范围，就要进行多次 IO *** 作 了。

所以，我们根据 页 的大小计算 m 的大小是再合适不过的了：

事实上，这种结构的树，就是 B+树 了

随着数据的插入或者删除，B+树 的节点也会不断变化，当节点过大或过小时，就需要对树中的节点进行合并或删除。

至此，B+树 的构建就基本完成了，你有没有发现它的结构和跳表很像呢？

以上就是本节的所有内容，希望对你有所帮助。

---