在MySQL中实现二分查找的详细教程

给定一个升序排列的自然数数组，数组中包含重复数字，例如：[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

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

赞 (0)

相关推荐

  • mysql查找删除重复数据并只保留一条实例详解

    有这样一张表,表数据及结果如下: school_id school_name total_student test_takers 1239 Abraham Lincoln High School 55 50 1240 Abraham Lincoln High School 70 35 1241 Acalanes High School 120 89 1242 Academy Of The Canyons 30 30 1243 Agoura High School 89 40 1244 Agour

  • C#中实现查找mysql的安装路径

    1.c#可以调用msyql的导入导出命令,但是需要先判断客户机是否安装了mysql,及其安装mysql的路径问题. 2.查询mysql安装路径的函数 复制代码 代码如下: private string GetMysqlPath()         {             string strPath = string.Empty;             string strsql = "select @@basedir as basePath from dual ";      

  • MySQL 中查找含有目标字段的表的方法

    复制代码 代码如下: SELECT TABLE_SCHEMA,TABLE_NAME FROM information_schema.`COLUMNS` WHERE COLUMN_NAME='字段名字' 参考:MySQL中,一个字段在多张表都存在,怎么用sql语句一次性查询这些表呢

  • mysql data文件夹位置查找

    找到自己的mysql数据库的安装位置,如下 C:\Program Files\MySQL\MySQL Server 5.1,在它里面有个的my.ini文件,寻找如下行: [mysqld] 复制代码 代码如下: # The TCP/IP Port the MySQL Server will listen on port=3306 #Path to installation directory. All paths are usually resolved relative to this. bas

  • 在MySQL中同时查找两张表中的数据的示例

    这个例子里面我们从两个表中取出头两行,然后合并到一个表中. 在现实中我们常常会遇到这样的情况,在一个数据库中存在两个表,假设表1储存着公司个产品本季度销售信息,表2储存着公司本季度欠款金额情况.在一个页面中我们想把这两个信息显示出来.通常的做法是在程序中进行两次SQL查询,返回两个结果集,在分别显示出来,非常麻烦. 下面是实现这个功能的代码: CREATE PROCEDURE test AS SET NOCOUNT ON --指示存储过程不返回查询影响的行数 DECLARE @col1c var

  • 查找MySQL线程中死锁的ID的方法

    如果遇到死锁了,怎么解决呢?找到原始的锁ID,然后KILL掉一直持有的那个线程就可以了, 但是众多线程,可怎么找到引起死锁的线程ID呢? MySQL 发展到现在,已经非常强大了,这个问题很好解决. 直接从数据字典连查找. 我们来演示下. 线程A,我们用来锁定某些记录,假设这个线程一直没提交,或者忘掉提交了. 那么就一直存在,但是数据里面显示的只是SLEEP状态. mysql> set @@autocommit=0; Query OK, 0 rows affected (0.00 sec) mys

  • mysql 数据表中查找重复记录

    复制代码 代码如下: select user_name,count(*) as count from user_table group by user_name having count>1; 这个我在很早有发过一个asp下的ACCESS 的

  • MySQL优化之如何查找SQL效率低的原因

    查询到效率低的 SQL 语句 后,可以通过 EXPLAIN 或者 DESC 命令获取 MySQL 如何执行 SELECT 语句的信息,包括在 SELECT 语句执行过程中表如何连接和连接的顺序,比如我们想计算 2006 年所有公司的销售额,需要关联 sales 表和 company 表,并且对 profit 字段做求和( sum )操作,相应 SQL 的执行计划如下: mysql> explain select sum(profit) from sales a,company b where a

  • 在MySQL中实现二分查找的详细教程

    给定一个升序排列的自然数数组,数组中包含重复数字,例如:[1,2,2,3,4,4,4,5,6,7,7].问题:给定任意自然数,对数组进行二分查找,返回数组正确的位置,给出函数实现.注:连续相同的数字,返回第一个匹配位置还是最后一个匹配位置,由函数传入参数决定. 我为什么会出这道题目? 二分查找在数据库内核实现中非常重要 在数据库的内核实现中,二分查找是一个非常重要的逻辑,几乎99%以上的SQL语句(所有索引上的范围扫描/等值查询/Unique查询等),都会使用到二分查找进行数据的定位. 考虑一个

  • mysql中binlog_format模式与配置详细分析

    mysql复制主要有三种方式:基于SQL语句的复制(statement-based replication, SBR),基于行的复制(row-based replication, RBR),混合模式复制(mixed-based replication, MBR).对应的,binlog的格式也有三种:STATEMENT,ROW,MIXED. ① STATEMENT模式(SBR) 每一条会修改数据的sql语句会记录到binlog中.优点是并不需要记录每一条sql语句和每一行的数据变化,减少了binl

  • MySql中sql语句执行过程详细讲解

    目录 前言: sql语句的执行过程: 查询缓存: 分析器: 优化器: 执行器: 总结 前言: 很多人都在使用mysql数据库,但是很少有人能够说出来整个sql语句的执行过程是怎样的,如果不了解执行过程的话,就很难进行sql语句的优化处理,也很难设计出来优良的数据库表结构.这篇文章主要是讲解一下sql语句的执行过程. sql语句的执行过程: 客户端.连接器.分析器.优化器.执行器.存储引擎几个阶段. 连接器的作用:管理链接.权限验证的处理. 分析器的作用:词法分析.语法分析. 优化器的作用:执行计

  • MySql 5.6.35 winx64 安装详细教程

    说明:因为数据库版本问题出现的项目启动没有错误,但是操作数据库的过程出现错误,为了保持数据库一致,重新检索到了安装mysql5.6的教程,不复杂,需要耐心. 若笔记本原本安装了其他数据库版本,请先将mysql数据库卸载干净,具体请参见网址:http://materliu.github.io/all/web/database/mysql/2014/04/24/uninstall-mysql-totaly.cm.html 为了防止网址不能访问或者不存在的情况,具体步骤如下: 1.首先在windows

  • NodeJS中的MongoDB快速入门详细教程

    MongoDB 是一个基于分布式文件存储的数据库.由 C++ 语言编写.旨在为 WEB 应用提供可扩展的高性能数据存储解决方案. MongoDB 是一个介于关系数据库和非关系数据库之间的产品,是非关系数据库当中功能最丰富,最像关系数据库的. 一.MongoDB必须理解的概念 1.数据库:每个数据库都有自己的权限和集合. 2.文档:一个键值对. 3.集合:一组文档,即一组键值对.当第一个文档插入时,集合就会被创建. 二.Mac下的MongoDB安装和启动 1.使用brew进行安装:brew ins

  • MySQL解压版配置步骤详细教程

    mysql-5.7.14-winx64\bin配置到Path中 在解压路径下复制my-default.ini,修改名称为my.ini 在my.ini添加如下 [mysqld] basedir=C:\\software\Mysql\mysql-5.7.14-winx64 datadir=C:\\software\Mysql\mysql-5.7.14-winx64\data port=3306 basedir:是上述mysql的解压路径 datadir:后续初始化等数据都会保存在该目录下,在该文件目

  • mysql 8.0.20 安装配置详细教程

    本文为大家分享了mysql 8.0.20 安装配置详细教程,供大家参考,具体内容如下 1.下载mysql8.0.20安装包 MySQL官网:链接 直接点击链接也可以下载:mysql 8.0.20 找到安装包后下载.(官网为英文,如果看不懂的小伙伴可以将网站复制到谷歌进行翻译) 点击跳过登录,直接下载到本地. 安装mysql1.下载下来之后是一个zip的压缩包文件 将其解压. 2.解压之后,接下来设置环境变量 右击我的电脑===>点击属性===>点击高级系统设置===>环境变量===>

  • python中spy++的使用超详细教程

    python中spy++的使用超详细教程

    1.spy++的基本操作 我们下载spy++: Microsoft Spy++ V15.0.26724.1 简体中文绿色版 64位 1.1 窗口属性查找 拖住中间的"寻找工具"放到想要定位的软件上,然后松开 以微信为例,我们会得到"微信"这个窗口的句柄,为"00031510",注意这个句柄是"十六进制",即"0x31510". 点击ok我们会看到更详细的属性信息 1.2 窗口spy++定位 同理拖放到&qu

  • 在Sublime Editor中配置Python环境的详细教程

    了解如何 在sublime编辑器中安装python软件包,以 实现自动完成等功能,并在sublime编辑器本身中运行build. 安装Sublime软件包控制 首先下载用于sublime编辑器的程序包控件. 转到URL: https : //packagecontrol.io/installation#st3 崇高包装控制 现在记下Sublime Editor中安装软件包的文件夹的位置.您可以通过单击 首选项>浏览包 来找到位置. 浏览套餐 单击" Package Control.subl

  • 在IDEA2020.2中配置使用Git的详细教程

    一. idea中配置git 先配置好git的本地地址,然后test,出现版本号说明测试成功! 二. idea中使用git 可以直接在idea中使用命令操作git 1.初始化本地仓库 选好项目点击OK即可. 2.添加到暂存区 3.提交到本地仓库 也可以在这里提交,效果一样只是位置不一样 4.推送至远程仓库 5.直接克隆项目到本地 6.拉取项目到本地 7.创建分支 这时候就切换到了新创建的分支 到此这篇关于在IDEA2020.2中配置使用Git的详细教程的文章就介绍到这了,更多相关idea配置使用g

随机推荐