APP推广合作
联系“鸟哥笔记小乔”
海量数据超快查询的秘密-跳表思想 by彭文华
2021-02-14 23:32:46

这是彭文华的第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


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

大数据架构师
分享到朋友圈
收藏
收藏
评分

综合评分:

我的评分
Xinstall 15天会员特权
Xinstall是专业的数据分析服务商,帮企业追踪渠道安装来源、裂变拉新统计、广告流量指导等,广泛应用于广告效果统计、APP地推与CPS/CPA归属统计等方面。
20羽毛
立即兑换
一书一课30天会员体验卡
领30天VIP会员,110+门职场大课,250+本精读好书免费学!助你提升职场力!
20羽毛
立即兑换
顺丰同城急送全国通用20元优惠券
顺丰同城急送是顺丰推出的平均1小时送全城的即时快送服务,专业安全,准时送达!
30羽毛
立即兑换
大数据架构师
大数据架构师
发表文章269
历任多家公司大数据总监、大数据架构师,专注于数字化转型领域。
确认要消耗 羽毛购买
海量数据超快查询的秘密-跳表思想 by彭文华吗?
考虑一下
很遗憾,羽毛不足
我知道了

我们致力于提供一个高质量内容的交流平台。为落实国家互联网信息办公室“依法管网、依法办网、依法上网”的要求,为完善跟帖评论自律管理,为了保护用户创造的内容、维护开放、真实、专业的平台氛围,我们团队将依据本公约中的条款对注册用户和发布在本平台的内容进行管理。平台鼓励用户创作、发布优质内容,同时也将采取必要措施管理违法、侵权或有其他不良影响的网络信息。


一、根据《网络信息内容生态治理规定》《中华人民共和国未成年人保护法》等法律法规,对以下违法、不良信息或存在危害的行为进行处理。
1. 违反法律法规的信息,主要表现为:
    1)反对宪法所确定的基本原则;
    2)危害国家安全,泄露国家秘密,颠覆国家政权,破坏国家统一,损害国家荣誉和利益;
    3)侮辱、滥用英烈形象,歪曲、丑化、亵渎、否定英雄烈士事迹和精神,以侮辱、诽谤或者其他方式侵害英雄烈士的姓名、肖像、名誉、荣誉;
    4)宣扬恐怖主义、极端主义或者煽动实施恐怖活动、极端主义活动;
    5)煽动民族仇恨、民族歧视,破坏民族团结;
    6)破坏国家宗教政策,宣扬邪教和封建迷信;
    7)散布谣言,扰乱社会秩序,破坏社会稳定;
    8)宣扬淫秽、色情、赌博、暴力、凶杀、恐怖或者教唆犯罪;
    9)煽动非法集会、结社、游行、示威、聚众扰乱社会秩序;
    10)侮辱或者诽谤他人,侵害他人名誉、隐私和其他合法权益;
    11)通过网络以文字、图片、音视频等形式,对未成年人实施侮辱、诽谤、威胁或者恶意损害未成年人形象进行网络欺凌的;
    12)危害未成年人身心健康的;
    13)含有法律、行政法规禁止的其他内容;


2. 不友善:不尊重用户及其所贡献内容的信息或行为。主要表现为:
    1)轻蔑:贬低、轻视他人及其劳动成果;
    2)诽谤:捏造、散布虚假事实,损害他人名誉;
    3)嘲讽:以比喻、夸张、侮辱性的手法对他人或其行为进行揭露或描述,以此来激怒他人;
    4)挑衅:以不友好的方式激怒他人,意图使对方对自己的言论作出回应,蓄意制造事端;
    5)羞辱:贬低他人的能力、行为、生理或身份特征,让对方难堪;
    6)谩骂:以不文明的语言对他人进行负面评价;
    7)歧视:煽动人群歧视、地域歧视等,针对他人的民族、种族、宗教、性取向、性别、年龄、地域、生理特征等身份或者归类的攻击;
    8)威胁:许诺以不良的后果来迫使他人服从自己的意志;


3. 发布垃圾广告信息:以推广曝光为目的,发布影响用户体验、扰乱本网站秩序的内容,或进行相关行为。主要表现为:
    1)多次发布包含售卖产品、提供服务、宣传推广内容的垃圾广告。包括但不限于以下几种形式:
    2)单个帐号多次发布包含垃圾广告的内容;
    3)多个广告帐号互相配合发布、传播包含垃圾广告的内容;
    4)多次发布包含欺骗性外链的内容,如未注明的淘宝客链接、跳转网站等,诱骗用户点击链接
    5)发布大量包含推广链接、产品、品牌等内容获取搜索引擎中的不正当曝光;
    6)购买或出售帐号之间虚假地互动,发布干扰网站秩序的推广内容及相关交易。
    7)发布包含欺骗性的恶意营销内容,如通过伪造经历、冒充他人等方式进行恶意营销;
    8)使用特殊符号、图片等方式规避垃圾广告内容审核的广告内容。


4. 色情低俗信息,主要表现为:
    1)包含自己或他人性经验的细节描述或露骨的感受描述;
    2)涉及色情段子、两性笑话的低俗内容;
    3)配图、头图中包含庸俗或挑逗性图片的内容;
    4)带有性暗示、性挑逗等易使人产生性联想;
    5)展现血腥、惊悚、残忍等致人身心不适;
    6)炒作绯闻、丑闻、劣迹等;
    7)宣扬低俗、庸俗、媚俗内容。


5. 不实信息,主要表现为:
    1)可能存在事实性错误或者造谣等内容;
    2)存在事实夸大、伪造虚假经历等误导他人的内容;
    3)伪造身份、冒充他人,通过头像、用户名等个人信息暗示自己具有特定身份,或与特定机构或个人存在关联。


6. 传播封建迷信,主要表现为:
    1)找人算命、测字、占卜、解梦、化解厄运、使用迷信方式治病;
    2)求推荐算命看相大师;
    3)针对具体风水等问题进行求助或咨询;
    4)问自己或他人的八字、六爻、星盘、手相、面相、五行缺失,包括通过占卜方法问婚姻、前程、运势,东西宠物丢了能不能找回、取名改名等;


7. 文章标题党,主要表现为:
    1)以各种夸张、猎奇、不合常理的表现手法等行为来诱导用户;
    2)内容与标题之间存在严重不实或者原意扭曲;
    3)使用夸张标题,内容与标题严重不符的。


8.「饭圈」乱象行为,主要表现为:
    1)诱导未成年人应援集资、高额消费、投票打榜
    2)粉丝互撕谩骂、拉踩引战、造谣攻击、人肉搜索、侵犯隐私
    3)鼓动「饭圈」粉丝攀比炫富、奢靡享乐等行为
    4)以号召粉丝、雇用网络水军、「养号」形式刷量控评等行为
    5)通过「蹭热点」、制造话题等形式干扰舆论,影响传播秩序


9. 其他危害行为或内容,主要表现为:
    1)可能引发未成年人模仿不安全行为和违反社会公德行为、诱导未成年人不良嗜好影响未成年人身心健康的;
    2)不当评述自然灾害、重大事故等灾难的;
    3)美化、粉饰侵略战争行为的;
    4)法律、行政法规禁止,或可能对网络生态造成不良影响的其他内容。


二、违规处罚
本网站通过主动发现和接受用户举报两种方式收集违规行为信息。所有有意的降低内容质量、伤害平台氛围及欺凌未成年人或危害未成年人身心健康的行为都是不能容忍的。
当一个用户发布违规内容时,本网站将依据相关用户违规情节严重程度,对帐号进行禁言 1 天、7 天、15 天直至永久禁言或封停账号的处罚。当涉及欺凌未成年人、危害未成年人身心健康、通过作弊手段注册、使用帐号,或者滥用多个帐号发布违规内容时,本网站将加重处罚。


三、申诉
随着平台管理经验的不断丰富,本网站出于维护本网站氛围和秩序的目的,将不断完善本公约。
如果本网站用户对本网站基于本公约规定做出的处理有异议,可以通过「建议反馈」功能向本网站进行反馈。
(规则的最终解释权归属本网站所有)

我知道了
恭喜你~答对了
+5羽毛
下一次认真读哦
成功推荐给其他人
+ 10羽毛
评论成功且进入审核!审核通过后,您将获得10羽毛的奖励。分享本文章给好友阅读最高再得15羽毛~
(羽毛可至 "羽毛精选" 兑换礼品)
好友微信扫一扫
复制链接