海量数据超快查询的秘密-跳表思想by彭文华林生斌是什么人物

这是彭文华的第163篇原创

今天是初三，恰逢情人节，也没提前准备啥礼物，就陪媳妇回娘家探亲。老丈人家一堆的小朋友，非常热闹。

我家娃是个孩子王，往年都用暴力征服小朋友，今年居然动脑筋了。他给一堆孩子出了一个题，是这样的：

随便来一个小朋友，心里想一个1-1000的数，他通过10个问题，猜出心中的那个数是多少。如果10个问题问完，猜中了，就得给他捶背5分钟。

过年做客么，除了聊天也没啥事，我就在旁边观察了半天，发现我家娃用一招搞定了所有小朋友，不仅享受了很久的“捶背”服务，还成为新晋“孩子王”。

他用的是啥招呢？其实是一个非常简单的方法-二分法。有些算法基础比较好的同学已经知道怎么回事了。你听我慢慢讲。

对了，我在挑战春节不打烊，每天都分享原创文章，欢迎加我个人微信：shirenpengwh，加入催更群，小鞭子催我快快写稿

二分查找

二分查找，也叫折半查找，是一个非常高效的查找方法。简单来说，就是通过多次减半查找，缩小数据范围，最终找到想找的那个数据。

就拿我儿子的那道题来说，目标是在10个问题之后，准确得知你心中想的那个1-1000之间的那个数字，具体操作方法如下：

问题1：这个数字是大于500对吗？无论答案是“是”还是“否”，都直接排除掉另外500个数字，这是第一次“折半”。咱假设是小于500.

问题2：这个数字是在1-250之间对吗？同样，无论答案是什么，都再次排除掉250个数字。这是第二次“折半”。

以此类推，10个问题问完，答案自然就出来了。为了节省篇幅，我编了一个excel表，你应该能快速看明白。

因为回答是什么都无所谓，我们都可以排除掉相应数量的错误答案。经过10个问题之后，就能排除999个答案，剩下那个自然就是正确答案了。

如果你数字足够敏感，就会发现，其实1000这个数字其实可以扩展到1024，也一样能达到效果，因为2的10次方就等于1024啊。1024对半砍10次，就能确定某个数字。

这个回答好像很简单？其实这是非常厉害的方法。一般人会怎么做？基本上就一个方法：瞎猜。因为另外一个方法基本没人用，就是从1开始，挨个猜，就是穷举法，感觉太笨了。

但是这两种方法效率都非常慢，因此非常不推荐。其实按个猜的这种穷举法，其实就是数据库中的全表扫描，速度自然是非常非常慢的。

而二分法这种思想，拓展一下就是跳表，也就是索引的核心思想。

跳表其实就是一个不断问数据库问题的方法，能够快速锁定数据所在的位置。

你看，这个跳表跟我儿子玩的那个猜数字的游戏多像啊？其实就是因为核心思想是一样的。对于海量数据，我们只需要对序号进行多层级的“折半查找”，就能快速锁定数据所在的地方，而不用挨个找。

不过我这张图画的不好，有人会问，这从1开始找不是第二条就找到了么？咱看图看意哈，这个思想可以搞定千万、亿级甚至更多数据的快速查找和锁定。

这种方法耗费的存储量也很小，因为只需要存储id就行，而且层级越往上，存储的数据就越少。

这个解决方案其实就是我们说的“索引”。而那么多问题其实就是一级索引、二级索引、三级索引。

当然，在数据库实际的使用中，还会遇到各种问题，比如插入新数据了，删掉老数据了。当某个老区域中的数据插入过多之后，这个区域的索引就不好使了，查询到这边的时候速度就会变慢。这就是插入、删除数据频繁的表，我们需要过一些时间就重建索引的原因。

跳表思想广泛应用于各个领域，当然应用最多的当然是数据领域了。别的不说，关系型数据库的索引就是跳表思想，MySQL面试题中肯定有这个的。算法题里也有大量跳表思想的题，实现方式也很简单，写个循环，不断/2就行了。

熟悉Redis的同学，应该知道对有序集合额（zset）的操作中国，就有按照范围区间查找元素的操作，这就是用跳表搞定的，效率非常高。

另外，Hbase MemStore的内部存储就是用跳表思想搞定的。Hbase实时写数据会先扔到内存里，然后再通过flush机制刷写到磁盘，生成StoreFile有序文件。跳表天然有序，并且查找、插入、删除性能都非常高，Hbase当然就拿来就用了。这也是Hbase查询效率超高的原因之一。

如果你想搞定女朋友，也可以用这个方法，让她心中想一个数字，然后用二分法，十次锁定答案，然后你就可以嘿嘿嘿...

二分法进一步扩展，就是跳表思想，对一个顺序链表提取多层索引，通过少量存储消耗，极强的增加查询效率。二分法30层就可以覆盖10亿条数据，这个量级就很恐怖了。

跳表思想广泛应用于各种查询领域，传统关系型数据库的索引就用了跳表思想。内存（缓存）数据库Redis也用了跳表实现查找元素的操作。大数据组件中专攻快速查询的Hbase组件的MemStore内部存储也用的跳表思想，这也是Hbase查询速度超远的原因之一。

今天的分享就是这样。欢迎大家加我个人微信号：shirenpengwh ，一起探讨大数据、数据分析相关知识。每天分享一篇原创内容给大家，我们一起学习，共同进步。

配合以下文章享受更佳

【详解】Flink的窗口类型详解

【详解】 | MapReduce环形缓冲区

【详解】| Flink的Checkpoints机制详解

【干货】架构师带你细细的捋一遍MapReduce全流程

【全解】一口气说完MR、Storm、Spark、SparkStreaming和Flink

我需要你的转发，小小的满足一下我的虚荣心