位置: 编程技术 - 正文

在MySQL中实现二分查找的详细教程(mysql第二章)

编辑:rootadmin

推荐整理分享在MySQL中实现二分查找的详细教程(mysql第二章),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:mysql 2pc,mysql怎么实现,mysql die,mysql有两种操作方式,mysql有两种操作方式,mysql2,mysql die,mysql die,内容如对您有帮助,希望把文章链接给更多的朋友!

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

我为什么会出这道题目?

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

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

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

SQL1:

SQL2:

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

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

SQL3:

SQL4:

由于数据库索引同时支持反向扫描,因此SQL3、SQL4的语句,都可以使用索引反向扫描。反向扫描时,SQL3需要定位到索引中的第一个2;而SQL4,则需要定位到索引的最后一个2,然后开始反向返回满足查询条件的索引记录。 二分查找在程序设计中,是一个十分基础并且易错的功能

第一个真正正确的二分查找算法,在第一个二分查找实现之后的年,才被发表出来。通过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,不存在溢出的问题。

在MySQL中实现二分查找的详细教程(mysql第二章)

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

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

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

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

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

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

数据库中的二分查找,更为复杂,需要实现一个通用型的二分查找算法,使用于各种不同的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

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

在MySQL中使用STRAIGHT_JOIN的教程 问题通过「SHOWFULLPROCESSLIST」语句很容易就能查到问题SQL,如下:SELECTpost.*FROMpostINNERJOINpost_tagONpost.id=post_tag.post_idWHEREpost.status=1ANDpost_tag.tag_id=ORDERBYpost.

探究MySQL优化器对索引和JOIN顺序的选择 本文通过一个案例来看看MySQL优化器如何选择索引和JOIN顺序。表结构和数据准备参考本文最后部分"测试环境"。这里主要介绍MySQL优化器的主要执行流程

使用Python的Django框架中的压缩组件Django Compressor 为了加快网站的加载速度,我们通常要多js和css进行压缩处理。这些js和css的压缩工作如果都手动处理,费时费力。DjangoCompressor可以实现js/css的自动压缩

标签: mysql第二章

本文链接地址:https://www.jiuchutong.com/biancheng/347693.html 转载请保留说明!

上一篇:MySQL中删除重复数据的简单方法(mysql删除重复的id但各保留一个)

下一篇:在MySQL中使用STRAIGHT_JOIN的教程

  • 税务师补报名时间可以交费吗
  • 计提税额与实缴税额的区别是什么?
  • 小规模纳税人的账务处理
  • 领用库存商品用于固定资产
  • 无形资产减值准备可以转回吗
  • 基本户可以直接转账给个人吗
  • 个人所得税申报是公司申报还是个人申报
  • 以公司名义买50万的车可以省多少钱
  • 公司收到待报解预算收入退的款是什么
  • 支付职工医疗保险怎么查
  • 其他综合收益何时转投资收益
  • 应付票据的处理
  • 资产减值准备怎么转回
  • 开出银行汇票支付手续费
  • 分摊材料成本差异的会计处理
  • 京东电子商务平台业务流程
  • 房地产增值税预征率
  • 个体工商户营业执照年检
  • 企业所得税计提分录怎么写
  • 两家公司合租一个房子
  • 季度所得税可以不预缴吗
  • 小规纳税人租金可以记入成本吗
  • 内部交易进项税怎么算
  • 超市收代金券如何处理
  • 坏账准备和资产减值损失
  • mac怎么还原出厂设置
  • 苹果Mac系统怎么用光盘安装
  • 税负率的计算方法公式
  • mac切换不了中文怎么回事
  • 老板垫付的员工怎么入账
  • Yii2.0小部件GridView(两表联查/搜索/分页)功能的实现代码
  • php正则表达式实例
  • 两险征缴工作的意义
  • 付境外人员劳务费
  • 固定资产进项税额怎么抵扣
  • 增值税专用发票查询系统官方网站
  • 手写发票可以报税吗
  • 腾讯云验证码服务
  • 微信小程序怎么制作自己的小程序
  • 商贸公司如何结转销售成本
  • 个体工商户缴税吗?
  • 拓展训练属于培训费吗
  • 以前年度收入少计如何做帐
  • mongodb中主键的默认格式是哪个?
  • 企业工会经费计提标准
  • 发票含税和不含税的区别
  • 产权出典是啥意思
  • 小规模纳税人有哪些
  • 稳岗补贴支付范围
  • 金税盘抵增值税
  • 货物已发出可以退款吗
  • 没有发票如何做会计分录
  • 工程外地预缴会计分录
  • 建筑业暂估成本票来了后的账务处理
  • 社保退休金计算方法
  • 这个月要交增值税怎么做账务处理
  • 民办非企业单位什么意思
  • 企业差旅费的报销流程
  • 已核销的坏账又收回预算会计分录
  • 生产的半成品怎么做分录
  • 销售方开具的红字专票怎么入账
  • 采购人员垫付怎么入账
  • ゆうちょ银行转账步骤
  • 会计账户分类是什么意思
  • sqlgun
  • win7资源管理器未响应怎么办
  • cmd命令 cd
  • memory在电脑里是什么意思
  • windows 如何解密
  • newsupd.exe - newsupd是什么进程 有什么用
  • Win10 RS1 14267 SDK版本发布下载
  • nodejs游戏开发
  • python文本处理教程
  • django实时刷新日志前端
  • unity ui批处理
  • java模拟浏览器点击
  • 西安房屋契税退税政策2020年
  • 河北省税务局对外公开电话
  • 如何当好一名税务局长
  • 中国十大经济农村
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设