MYSQL数据库在MySQL中实现二分查找的详细教程
|
《MYSQL数据库在MySQL中实现二分查找的详细教程》要点： MYSQL必读给定一个升序排列的自然数数组,数组中包含重复数字,例如：[1,2,3,4,5,6,7,7].问题：给定任意自然数,对数组进行二分查找,返回数组正确的位置,给出函数实现.注：连续相同的数字,返回第一个匹配位置还是最后一个匹配位置,由函数传入参数决定. MYSQL必读我为什么会出这道题目? MYSQL必读??? 二分查找在数据库内核实现中非常重要 MYSQL必读??? 在数据库的内核实现中,二分查找是一个非常重要的逻辑,几乎99%以上的SQL语句(所有索引上的范围扫描/等值查询/Unique查询等),都会使用到二分查找进行数据的定位. MYSQL必读??? 考虑一个数据库表t1(a int primary key,b int),表上的b字段有一个B+树索引,表中记录的b字段取值,就是题目中的[1,7]序列.此时,给定以下的两条查询语句,就是使用到了不同的二分查找逻辑： MYSQL必读??? SQL1：?? MYSQL必读
select * from t1 where b > 4;
MYSQL必读??? SQL2：? MYSQL必读
select * from t1 where b >= 4;
MYSQL必读??? 针对SQL1,索引的二分查找,就需要跳过所有的4,从最后一个4之后开始返回所有记录；针对SQL2,二分查找就需要定位到第一个4,然后顺序读取所有记录. MYSQL必读??? 除此之外,针对数据库中其他的查询逻辑,二分查找还需要附带更多的功能,例如： MYSQL必读??? SQL3：? MYSQL必读
select * from t1 where b < 2;
MYSQL必读??? SQL4： MYSQL必读
select * from t1 where b <= 2;
MYSQL必读??? 由于数据库索引同时支持反向扫描,因此SQL3、SQL4的语句,都可以使用索引反向扫描.反向扫描时,SQL3需要定位到索引中的第一个2；而SQL4,则需要定位到索引的最后一个2,然后开始反向返回满足查询条件的索引记录. MYSQL必读??? 第一个真正正确的二分查找算法,在第一个二分查找实现之后的12年,才被发表出来.通过Google,输入Binary Search或者是二分查找关键字,有大量的相关的文章或者博客讨论此话题. MYSQL必读二分查找实现,需要注意的问题 MYSQL必读本文不准备详细介绍一个正确的二分查找应该是如何实现的,毕竟现在网上有着大量的正确版本.接下来,根据批改试卷过程中发现的一些问题,做一些简单的分析,希望对大家实现一个有效的二分查找算法,甚至是一个数据库内可用的二分查找算法,有所帮助. MYSQL必读大量的试卷,在给出此问题的解决算法时,直接拿着low,high参数开始进行计算,但是却没有检查low/high参数.low/high是否相同,数组中是否存在记录?low/high构成的区间是否有效?代码的鲁棒性不足. MYSQL必读在数据库的二分查找实现中,一般是对一个索引页面进行二分查找.索引页面中有可能根本不存在用户的记录(索引页面中的记录全部被删除,又没有与兄弟页面合并时),此时,low/high均为0,此时如果根据low/high计算出来的mid进行记录的读取,就存在逻辑错误. MYSQL必读这是一个经典的话题,如何计算二分查找中的中值?试卷中,大家一般给出了两种计算方法： MYSQL必读算法一： mid = (low + high) / 2 MYSQL必读算法二： mid = low + (high C low)/2 MYSQL必读乍看起来,算法一简洁,算法二提取之后,跟算法一没有什么区别.但是实际上,区别是存在的.算法一的做法,在极端情况下,(low + high)存在着溢出的风险,进而得到错误的mid结果,导致程序错误.而算法二能够保证计算出来的mid,一定大于low,小于high,不存在溢出的问题. MYSQL必读回到数据库二分查找,数据库的一个索引页面(大小一般是8k或者是16k),能够存储的索引记录是有限的,因此肯定不会出现(low + high)溢出的风险.这也是为什么InnoDB中的中值,采用的就是算法一的实现.但是,作为一个严谨的程序设计人员,还是推荐使用算法二,将任何潜在的风险,扼杀于摇篮之中. MYSQL必读超过一半的试卷,使用了递归调用的方式实现二分查找.不能说递归实现有错,而是在于实现效率问题.总所周知,递归调用存在着压栈/出栈的开销,其效率是比较低下的.而以数据库这样一个极端优化代码效率,提供快速查询响应的系统来说,效率是第一位的.不建议使用递归方式实现二分查找,至少在数据库内核实现中是不允许使用的.据我所知,所有的开源数据库系统,例如：InnoDB,PostgreSQL都未采用递归方式实现二分查找. MYSQL必读回到题目,要求根据传入的参数不同,返回第一个/最后一个等值项.在本文的背景部分,我也解释了此问题对应的数据库查询(>,>=查询需求是不同的).在试卷中,超过80%的同学的答案都是先进行二分查找,待定位到相同值之后,再根据传入的flag(用户需求：flag = 1,返回第一个等值项；flag = 0,返回最后一个等值项),进行顺序遍历,直至定位到满足条件的项. MYSQL必读同样,不能说这个实现是错的,但是也存在着性能问题.性能性能性能,永远是数据库内核实现考虑的重点之一(相信也是所有应用程序的一个指标).数据库中,除了主键索引/Unique索引能够保证键值唯一之外,很多二级辅助索引都是存在相同键值的,有时相同键值的项会超过千项(考虑一个用户的订单,或者是购买记录). MYSQL必读假设一个索引页面,保存着400项记录,均为相同键值.此时,使用先二分查找,后顺序遍历的算法,二分查找只能使用一次,顺序遍历199次,最终对比了200次.效率非常之低.当然,我也欣喜的看到另外一小部分同学的做法(我期待看到的算法),用flag来纠正每次比较的最终结果.例如：比较相等(相等用0表示,大于为1,小于为-1),但是flag = 1,则返回纠正后的比较结果为1,需要移动二分查找的high到mid,继续二分(反之,若flag = 0,则返回纠正后的结果为-1,需要移动二分查找的low到mid,继续二分).如此一来,等值仍旧可以进行二分查找,最终的对比只需要9次,远远小于200次. MYSQL必读此问题,进一步引出了下一个问题,数据库中如何实现一个通用的,更为复杂的二分查找算法? MYSQL必读数据库中的二分查找,更为复杂,需要实现一个通用型的二分查找算法,使用于各种不同的SQL查询场景. MYSQL必读InnoDB针对不同的SQL语句,总结出四种不同的Search Mode,分别为： MYSQL必读#define??? PAGE_CUR_G????????? 1??????? >查询 MYSQL必读#define??? PAGE_CUR_GE???????? 2??????? >=,=查询 MYSQL必读#define??? PAGE_CUR_L????????? 3??????? <查询 MYSQL必读#define??? PAGE_CUR_LE???????? 4??????? <=查询 MYSQL必读然后根据这四种不同的Search Mode,在二分查找碰到相同键值时进行调整.例如：若Search Mode为PAGE_CUR_G或者是PAGE_CUR_LE,则移动low至mid,继续进行二分查找；若Search Mode为PAGE_CUR_GE或者是PAGE_CUR_L,则移动high至mid,继续进行二分查找. MYSQL必读我们的TNT引擎,采用了与InnoDB不同的方案,但是也实现了相同的功能.TNT引擎针对相同键值的调整总结为下图,在此我就不做解释了,大家可以尝试着自己进行分析. MYSQL必读/* 操作符 includeKey???? forward???? compare result: 1??? 0??????? -1 */ MYSQL必读============================================================================= MYSQL必读>=??????????? 1??????????? 1??? |??????????? 1??????????? -1??????? -1 MYSQL必读=???????????? 1??????????? 1??? |??????????? 1??????????? -1??????? -1 MYSQL必读>???????????? 0??????????? 1??? |??????????? 1???????????? 1??????? -1 MYSQL必读<???????????? 0??????????? 0??? |??????????? 1??????????? -1??????? -1 MYSQL必读<=??????????? 1??????????? 0??? |??????????? 1???????????? 1??????? -1 MYSQL必读============================================================================= （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |