二分查找(Binary Search)需要注意的问题,以及在数据库内核中的实现

标签: MySQL解错方案 二分查找 Binary | 发表时间:2013-06-18 21:58 | 作者:OurMySQL
出处:http://ourmysql.com

问题背景

今年的实习生招聘考试,我出了一道二分查找(Binary Search)的题目。题目大意如下:

给定一个升序排列的自然数数组,数组中包含重复数字,例如:[1,2,2,3,4,4,4,5,6,7,7]。问题:给定任意自然数,对数组进行二分查找,返回数组正确的位置,给出函数实现。注:连续相同的数字,返回第一个匹配位置还是最后一个匹配位置,由函数传入参数决定。

我为什么会出这道题目?

  • 二分查找在数据库内核实现中非常重要

在数据库的内核实现中,二分查找是一个非常重要的逻辑,几乎99%以上的SQL语句(所有索引上的范围扫描/等值查询/Unique查询等),都会使用到二分查找进行数据的定位。


考虑一个数据库表t1(a int primary key, b int),表上的b字段有一个B+树索引,表中记录的b字段取值,就是题目中的 [1,2,2,3,4,4,4,5,6,7,7]序列。此时,给定以下的两条查询语句,就是使用到了不同的二分查找逻辑:


SQL1:   select * from t1 where b > 4;

SQL2: select * from t1 where b >= 4;


针对SQL1,索引的二分查找,就需要跳过所有的4,从最后一个4之后开始返回所有记录;针对SQL2,二分查找就需要定位到第一个4,然后顺序读取所有记录。


除此之外,针对数据库中其他的查询逻辑,二分查找还需要附带更多的功能,例如:


SQL3: select * from t1 where b < 2;

SQL4: select * from t1 where b <= 2;


由于数据库索引同时支持反向扫描,因此SQL3、SQL4的语句,都可以使用索引反向扫描。反向扫描时,SQL3需要定位到索引中的第一个2;而SQL4,则需要定位到索引的最后一个2,然后开始反向返回满足查询条件的索引记录。


  • 二分查找在程序设计中,是一个十分基础并且易错的功能

    第一个真正正确的二分查找算法,在第一个二分查找实现之后的12年,才被发表出来。通过Google,输入 Binary Search或者是 二分查找关键字,有大量的相关的文章或者博客讨论此话题。

  • 二分查找实现,需要注意的问题

    本文不准备详细介绍一个正确的二分查找应该是如何实现的,毕竟现在网上有着大量的正确版本。接下来,根据批改试卷过程中发现的一些问题,做一些简单的分析,希望对大家实现一个有效的二分查找算法,甚至是一个数据库内可用的二分查找算法,有所帮助。

    问题一:是否检查参数的有效性

    大量的试卷,在给出此问题的解决算法时,直接拿着low,high参数开始进行计算,但是却没有检查low/high参数。low/high是否相同,数组中是否存在记录?low/high构成的区间是否有效?代码的鲁棒性不足。

    在数据库的二分查找实现中,一般是对一个索引页面进行二分查找。索引页面中有可能根本不存在用户的记录(索引页面中的记录全部被删除,又没有与兄弟页面合并时),此时,low/high均为0,此时如果根据low/high计算出来的mid进行记录的读取,就存在逻辑错误。

    问题二:二分查找中值的计算

    这是一个经典的话题,如何计算二分查找中的中值?试卷中,大家一般给出了两种计算方法:

    算法一: mid = (low + high) / 2

    算法二: mid = low + (high – low)/2

    乍看起来,算法一简洁,算法二提取之后,跟算法一没有什么区别。但是实际上,区别是存在的。算法一的做法,在极端情况下,(low + high)存在着溢出的风险,进而得到错误的mid结果,导致程序错误。而算法二能够保证计算出来的mid,一定大于low,小于high,不存在溢出的问题。

    回到数据库二分查找,数据库的一个索引页面(大小一般是8k或者是16k),能够存储的索引记录是有限的,因此肯定不会出现(low + high)溢出的风险。这也是为什么InnoDB中的中值,采用的就是算法一的实现。但是,作为一个严谨的程序设计人员,还是推荐使用算法二,将任何潜在的风险,扼杀于摇篮之中。

    问题三:递归实现二分查找

    超过一半的试卷,使用了递归调用的方式实现二分查找。不能说递归实现有错,而是在于实现效率问题。总所周知,递归调用存在着压栈/出栈的开销,其效率是比较低下的。而以数据库这样一个极端优化代码效率,提供快速查询响应的系统来说,效率是第一位的。不建议使用递归方式实现二分查找,至少在数据库内核实现中是不允许使用的。据我所知,所有的开源数据库系统,例如:InnoDB,PostgreSQL都未采用递归方式实现二分查找。

    问题四:如何查找第一个/最后一个等值

    回到题目,要求根据传入的参数不同,返回第一个/最后一个等值项。在本文的背景部分,我也解释了此问题对应的数据库查询(>,>=查询需求是不同的)。在试卷中,超过80%的同学的答案都是先进行二分查找,待定位到相同值之后,再根据传入的flag(用户需求:flag = 1,返回第一个等值项;flag = 0,返回最后一个等值项),进行顺序遍历,直至定位到满足条件的项。

    同样,不能说这个实现是错的,但是也存在着性能问题。性能性能性能,永远是数据库内核实现考虑的重点之一(相信也是所有应用程序的一个指标)。数据库中,除了主键索引/Unique索引能够保证键值唯一之外,很多二级辅助索引都是存在相同键值的,有时相同键值的项会超过千项(考虑一个用户的订单,或者是购买记录)。

    假设一个索引页面,保存着400项记录,均为相同键值。此时,使用先二分查找,后顺序遍历的算法,二分查找只能使用一次,顺序遍历199次,最终对比了200次。效率非常之低。当然,我也欣喜的看到另外一小部分同学的做法(我期待看到的算法),用flag来纠正每次比较的最终结果。例如:比较相等(相等用0表示,大于为1,小于为-1),但是flag = 1,则返回纠正后的比较结果为1,需要移动二分查找的high到mid,继续二分(反之,若flag = 0,则返回纠正后的结果为-1,需要移动二分查找的low到mid,继续二分)。如此一来,等值仍旧可以进行二分查找,最终的对比只需要9次,远远小于200次。

    此问题,进一步引出了下一个问题,数据库中如何实现一个通用的,更为复杂的二分查找算法?

    问题五:数据库中的二分查找实现举例

    数据库中的二分查找,更为复杂,需要实现一个通用型的二分查找算法,使用于各种不同的SQL查询场景。

    InnoDB针对不同的SQL语句,总结出四种不同的Search Mode,分别为:

    #define    PAGE_CUR_G          1        >查询

    #define    PAGE_CUR_GE         2        >=,=查询

    #define    PAGE_CUR_L          3        <查询

    #define    PAGE_CUR_LE         4        <=查询

    然后根据这四种不同的Search Mode,在二分查找碰到相同键值时进行调整。例如:若Search Mode为PAGE_CUR_G或者是PAGE_CUR_LE,则移动low至mid,继续进行二分查找;若Search Mode为PAGE_CUR_GE或者是PAGE_CUR_L,则移动high至mid,继续进行二分查找。

    我们的TNT引擎,采用了与InnoDB不同的方案,但是也实现了相同的功能。TNT引擎针对相同键值的调整总结为下图,在此我就不做解释了,大家可以尝试着自己进行分析。

    /* 操作符 includeKey     forward     compare result: 1     0        -1 */

    =============================================================================

    >=            1            1    |            1             -1        -1

    =             1            1    |            1             -1        -1

    >             0            1    |            1             1        -1

    <             0            0    |            1             -1        -1

    <=            1            0    |            1             1        -1

    =============================================================================

    总结

    本文通过一个二分查找的题目,以及同学们在解答题目中暴露出来的问题,分析了一个安全可靠高效的二分查找,应该注意哪些问题。并简要分析了数据库内核实现中的二分查找实现,希望对大家在以后设计二分查找算法时,有所帮助。

    抱歉猜想失败,您看看下面的文章有用吗?

    相关 [二分查找 binary search] 推荐:

    二分查找(Binary Search)需要注意的问题,以及在数据库内核中的实现

    - - OurMySQL
    今年的实习生招聘考试,我出了一道二分查找(Binary Search)的题目. 给定一个升序排列的自然数数组,数组中包含重复数字,例如:[1,2,2,3,4,4,4,5,6,7,7]. 问题:给定任意自然数,对数组进行二分查找,返回数组正确的位置,给出函数实现. 注:连续相同的数字,返回第一个匹配位置还是最后一个匹配位置,由函数传入参数决定.

    protobuf,json,xml,binary,Thrift之间的对比

    - - 学习笔记
    一条消息数据,用protobuf序列化后的大小是json的10分之一,xml格式的20分之一,是二进制序列化的10分之一,总体看来ProtoBuf的优势还是很明显的. protobuf是google提供的一个开源序列化框架,类似于XML,JSON这样的数据表示语言,详情访问protobuf的google官方网站 https://code.google.com/p/protobuf/.

    浅谈 Semantic Search

    - - IT瘾-dev
    顾名思义,关键词搜索就是当用户输入关键词( Query),搜索引擎会去搜索并匹配含有 Query的文档,然后返回相关的结果( Response). 一般来说,一个文档包含越多的用户关键词,它在结果中的排序就越靠前. 假设有以下的 Query和 Responses:. 我们可以观察 Responses中每个结果中的词与 Query 中的词,然后找出在  Query和   Response 都出现的词的个数:.

    数据交换格式protobuf/json/xml/binary/Thrift

    - - 互联网旁观者
    一条消息数据,用 protobuf序列化后的大小是 json的10分之一, xml格式的20分之一,是 二进制序列化的10分之一,总体看来ProtoBuf的优势还是很明显的. protobuf是google提供的一个开源序列化框架,类似于XML,JSON这样的数据表示语言,详情访问 protobuf的google官方网站.

    MySQL Fulltext Search 使用方式

    - - Tsung's Blog
    使用 MySQL 來達到 Fulltext 的效果, MySQL 對於 英文會自己依照空格去斷開, 中文就得要自行斷詞囉~. MySQL Fulltext Search 使用方式 與 注意事項. MySQL Fulltext 不支援 InnoDB, 需要使用 MyISAM.. 建立 Table 時, 需要設定 FULLTEXT(Col-name)..

    比普通二分查找快4倍的结构

    - GLORY - 构架师-搜索引擎-冲出宇宙(健健康康:http://www.zhaojk.com)
     二分查找是查询有序数组的有效结构,对于规模为N的有序数组来说,二分查找算法的时间复杂度为O(logN).  即每次选择数组范围的中间数据和查询数据比较,如果不等于查询数据则选择一半的范围继续查询.  算法每次选择一段范围的中间节点,每次都相当于一个随机位置比较,对cache和磁盘等非随机结构很不友好.

    二分查找法的实现和应用汇总

    - - 酷勤网-挖经验 [expanded by feedex.net]
    在学习算法的过程中,我们除了要了解某个算法的基本原理、实现方式,更重要的一个环节是利用big-O理论来分析算法的复杂度. 在时间复杂度和空间复杂度之间,我们又会更注重时间复杂度. 时间复杂度按优劣排差不多集中在:. 到目前位置,似乎我学到的算法中,时间复杂度是O(log n),好像就数二分查找法,其他的诸如排序算法都是 O(n log n)或者O(n.

    Steve Souders: In Search of Speed 学习笔记

    - arbeitandy - 知道分子
    原雅虎首席性能官、现任 Google Web 性能专家 Steve Souders,近期在 LA 隆重举行的 SpeedGeeks 会议上发表重要讲话:In Search of Speed(slides, video),以下为学习笔记:. 以 iGoogle 为例,前端页面组件渲染的时间占了整个页面打开时间的 91%,前端优化的重要性不言而喻.

    Google、「Buzz」や「Code Search」も終了へ

    - GOT4416 - ITmedia News 速報 最新記事一覧
    製品担当副社長のホロビッツ氏は、「Google Buzz」で学んだ多くのことを「Google+」に反映させていくと語った.

    Google Code Search 終了のお知らせ

    - 三十不归 - スラッシュドット・ジャパン
    ある Anonymous Coward 曰く、. SourceForge.JP Magazine の記事によると、Google はソースコード検索サービスである「Google Code Search」を 2012 年 1 月 15 日に終了するとのことだ. 主要サービスにいっそう集中していくための再編の一環で、「Google Buzz」や「Jaiku」など 5 つのプロジェクトが対象となっている.