来源丨经授权转自小白debug（ID：xiaobaidebug）
作者丨小白
在我们的印象中，mysql数据表里无非就是存储一行行的数据。跟个excel似的。
直接遍历这一行行数据，性能就是O(n)，比较慢。为了加速查询，使用了B+树来做索引，将查询性能优化到了O(lg(n))。
但问题就来了，查询数据性能在lg(n)级别的数据结构有很多，比如redis的zset里用到的跳表，也是lg(n)，并且实现还贼简单。
那为什么mysql的索引，不使用跳表呢？
我们今天就来聊聊这个话题。
B+树的结构之前的一篇文章里，已经提到过B+树的结构了。文章不长，如果没看过，建议先看下。
当然，不看也行。
在这里，为了混点字数，我简单总结下B+树的结构。
B+树查询过程如上图，一般B+树是由多个页组成的多层级结构，每个页16Kb，对于主键索引来说，最末级的叶子结点放行数据，非叶子结点放的则是索引信息（主键id和页号），用于加速查询。
比方说我们想要查找行数据5。会先从顶层页的record们入手。record里包含了主键id和页号（页地址）。