精华内容
下载资源
问答
  • 我们创建一个数组,通过N次比较,每次找出最大或最小的元素,把它放到队列最末尾就完成将无序数组转化成为了有序数组,这些排序都是再内存中进行的。 我们开发系统的时候,经常会有按照某种条件就行排序需求。你...

    前言

    学习编程语言的时候,我们第一个行代码往往是“Hello World”。我们学会的第一个真正意义上的算法,我想就是冒泡排序吧。我们创建一个数组,通过N次比较,每次找出最大或最小的元素,把它放到队列最末尾就完成将无序数组转化成为了有序数组,这些排序都是再内存中进行的。

    我们开发系统的时候,经常会有按照某种条件就行排序的需求。你有没有这样的疑问:我们的数据都是存放硬盘上的,如果数据有200G,但是我的内存只有16G,它是怎么排序的?

    今天我们带着这个疑问来看一看MySQL中“order by”是如何实现的。

    全字段排序

    首先我们创建一张表,里面插入4条元素

    CREATE TABLE `user` (
      `id` int(11) NOT NULL AUTO_INCREMENT,
      `name` varchar(24) CHARACTER SET utf8 DEFAULT NULL,
      `age` int(11) DEFAULT NULL,
      `city` varchar(64) CHARACTER SET utf8 DEFAULT NULL,
      PRIMARY KEY (`id`)
    ) ENGINE=InnoDB
    
    INSERT INTO `user` VALUES (1, '张三', 18, '成都');
    INSERT INTO `user` VALUES (2, '李四', 30, '西安');
    INSERT INTO `user` VALUES (3, '王五', 27, '杭州');
    INSERT INTO `user` VALUES (4, '赵六', 24, '深圳');

    如果我们要按照年龄对用户表进行降序排列只需要执行这条语句

    SELECT id, `name`, age from `user` order by age DESC;

    通过这条语句我们和容易的就得到了结果,我们查看一下它的执行计划

    Extra这个列中“Using filesort”表示需要排序,MySQL会给每一个线程分配一块内存用于排序,这块内存成为sort_buffer,具体怎么执行的我们看下图。

    1:初始化sort_buffer,确定需要字段为name,age

    2:根据条件获取User表中的数据,存入sort_buffer中

    3:对sort_buffer中的数据按照字段age进行快速排序

    4:将排序结果的结果集返回给客户端

    我们将这个动作暂时称为“全字段排序”,其中第3步“按照age进行快速排序”这个动作是再内存中完成的。但是如果需要排序的数量过大,内存放不下,则这时候就不得不利用磁盘临时文件辅助排序。

    sort_buffer_size这个参数就是sort_buffer的大小,如果超出这个值就需要借助文件辅助了。这时候MySQL会将需要排序的数据分成12份,没一个单独排序后存放在这些临时文件中。然后再把这12个有序文件合并成一个有序大文件。

    rowid排序

    上面算法的执行过程中把所有的数据读取出来,如果可以在内存中排序就使用sort_buffer,如果sort_buffer放不下就借助临时文件。但是又有一个问题,我们需要排序的行数不是特别多,但是要返回的数据行数特别多,这样的话sort_buffer里面要放的字段很多,很快就超出最大内存容量,这时候就退化成临时文件排序性能就会降低很多。

    如果单行太大,临时文件排序效率肯定不够好。MySQL中有一个参数max_length_for_sort_data是专门控制排序的行的长度的一个参数。它的意思是说,如果单行的长度超过了这个值,MySQL就认为单行太大,这时候就会换一个算法。

    我们name、age定义的长度是28,我们设置max_length_for_sort_data为16,这时候我们的算法就会变成另一种。

     

    1:初始化sort_buffer,确定需要字段为id,age

    2:根据条件获取User表中的数据,存入sort_buffer中

    3:对sort_buffer中的数据按照字段age进行快速排序

    4:根据sort_buffer中的id回表取出name、age构造结果集返回

    sort buffer中的字段只有需要排序的字段和id,和上个算法相比字段少了占用内存自然就少了,但是和之前相比多了一步回表。而“结果集”也是一个逻辑概念。MySQL服务端从排序后的sort_buffer中依次取出id,然后到原表查询就可以,不再需要服务端再耗费内存,而是直接返回给客户端。

    天然有序

    如果我们需要返回的数据本身就是有序的话,那么就不需要order by排序了。我们可以再user表上增加age、name的链接索引,

    alter table user add index age_name(age, name);

     

    这时候我们查看一下执行计划就会发现extra字段中没有Using filesort就是说明不需要排序,而Using index就说明使用了覆盖索引。覆盖索引是指,索引上的信息已经可以满足查询,不需要再回到主键索引上去取数据。

    前面基于age/name创建的联合索引它本身有序,所以需不要再把数据读入sort_buffer排序再返回,而是直接返回就可以了。

     

    最后,如果感觉对你有帮助就来个二连吧:关注、点赞!

     

    展开全文
  • 由于 Web端/数据库/判题机 全部被打包在同一个镜像,无法扩展,不推荐使用此镜像做分布式判题,另外请不要在 Docker 中使用 SHM 文件系统,会由于内存空间不足无法挂载沙箱环境而导致莫名其妙运行错误 部署后使用...
  • Collections是针对集合类一个帮助类,他提供一系列静态方法实现对各种集合搜索、排序、线程安全化等操作。 13、&和&&区别。 &是位运算符,表示按位与运算,&&是逻辑运算符,表示逻辑与(and)。 14、...
  • 因为树的高度是 logn, 也是二叉查找树所有形态中高度最小的树;我们试着来分析一下: <pre><code> // 对于一颗包含 n 个节点完全二叉树 // 1. 除了最后一层外,每一层的节点是上一层节点个数的2倍...
  • 3.5.4 字符数据在内存存储形式及使用方法 41 3.5.5 字符串常量 41 3.5.6 符号常量 42 3.6 变量赋初值 42 3.7 各类数值型数据之间混合运算 43 3.8 算术运算符和算术表达式 44 3.8.1 C运算符简介 44 3.8.2 算术...
  • (42) 希尔排序法属于哪一种类型的排序法(B) A.交换类排序法 B.插入类排序法 C.选择类排序法 D.建堆排序法 (43) 在深度为5的满二叉树中,叶子结点的个数为(C) A. 32 B. 31 C. 16 D. 15 (44) 对长度为N的线性表进行...
  • (14) 软件的需求分析阶段工作,可以概括为四个方面:______、需求分析、编写需求规格说明书和需求评审。 答:需求获取 (15) ______是数据库应用核心。 答:数据库设计 (16) 数据结构包括数据______结构和...
  • SQLServer2008查询性能优化 2/2

    热门讨论 2012-03-02 16:26:55
    4.8.1 不同排序顺序 135 4.8.2 在计算列上索引 136 4.8.3 BIT数据类型列上索引 136 4.8.4 作为一个查询处理CREATE INDEX语句 136 4.8.5 并行索引创建 136 4.8.6 在线索引创建 137 4.8.7 考虑数据库...
  • 大话数据结构

    2019-01-10 16:35:22
    求100个人高考成绩平均分与求全省所有考生成绩平均分在占用时间和内存存储上有非常大差异,我们自然追求高效率和低存储算法来解决问题。 2.6.1正确性 22 2.6.2可读性 23 2.6.3健壮性 23 2.6.4时间效率高和...
  • 大话数据结构 程杰

    2018-09-01 10:06:43
    求100个人高考成绩平均分与求全省所有考生成绩平均分在占用时间和内存存储上有非常大差异,我们自然追求高效率和低存储算法来解决问题。 2.6.1正确性 22 2.6.2可读性 23 2.6.3健壮性 23 2.6.4时间效率高和...
  • 2.5 算法特性 21 2.5.1 输入输出 21 2.5.2 有穷性 21 2.5.3 确定性 21 2.5.4 可行性 21 2.6 算法设计要求 22 求100个人高考成绩平均分与求全省所有考生成绩平均分在占用时间和内存存储上有非常大差异,...
  • 求100个人高考成绩平均分与求全省所有考生成绩平均分在占用时间和内存存储上有非常大差异,我们自然追求高效率和低存储算法来解决问题。 2.6.1正确性 22 2.6.2可读性 23 2.6.3健壮性 23 2.6.4时间效率高和...
  • 求100个人高考成绩平均分与求全省所有考生成绩平均分在占用时间和内存存储上有非常大差异,我们自然追求高效率和低存储算法来解决问题。 2.6.1正确性 22 2.6.2可读性 23 2.6.3健壮性 23 2.6.4时间效率高和...
  • 软件工程教程

    热门讨论 2012-07-06 23:10:29
    根据需求对系统进行定制外,为系统编写定制应用。 第二类开发者 在创业型公司或者是独立开发者,盈利方式主要2种: 为国外公司外包开发,或者通过Google移动广告(AdMob)点击分成。 通过付费下载形式来盈利...
  • 大话数据结构-程杰

    2014-07-13 23:45:52
    求100个人高考成绩平均分与求全省所有考生成绩平均分在占用时间和内存存储上有非常大差异,我们自然追求高效率和低存储算法来解决问题。 2.6.1 正确性 22 2.6.2 可读性 23 2.6.3 健壮性 23 2.6.4 时间...
  • java 面试题 总结

    2009-09-16 08:45:34
    Collections是针对集合类一个帮助类,他提供一系列静态方法实现对各种集合搜索、排序、线程安全化等操作。 10、&和&&区别。 &是位运算符,表示按位与运算,&&是逻辑运算符,表示逻辑与(and)。 11、HashMap...
  • Reason :跨平台框架,使开发者能够更容易地使用Java,.Net和Python,同时也满足了他们对C++性能和优势的需求。 ROOT :具备所有功能一系列面向对象框架,能够非常高效地处理和分析大量数据,为欧洲原子能...
  • delphi 开发经验技巧宝典源码

    热门讨论 2010-08-12 16:47:23
    0270 控制窗体最大化、最小化 178 0271 无标题栏时改变窗体大小 178 0272 无标题栏最大化时不覆盖任务栏 178 0273 限制窗体大小 179 0274 重定义去掉标题栏并最大化窗体 179 0275 使窗体一直居中 ...
  • UE免安装绿色版

    2015-12-24 19:46:03
    -文档大小不受限制,即使是数兆字节文件也只占用最小限度内存 -可同时打开和显示多个文档 -列模式编辑!!!插入列/删除/减切/添加序列 -拖放编译 -文件排序(包括删除重复文件,忽略大小写,升序,降序) -...
  • windowsnt 技术内幕

    2014-04-09 20:47:17
    使用User Mnager for Domains创建用户帐号 刷新用户帐号列表 用户帐号列表的排序 事件查看器(Event View)程序简介 筛选Event Viewer中的事件 授予用户在本地登录的权利 使用Windows NT诊断程序查看系统配置 激活...
  • JavaScript王者归来

    2013-01-10 11:30:48
    12.5.6 关于添加新行和排序的小技巧 12.6 读写数据--添加、修改和删除属性 12.7 外观与行为 12.7.1 DOM样式属性 12.7.2 控制DOM元素显示与隐藏 12.7.3 改变颜色和大小--一个简单有趣例子 12.7.4 改变位置--创建...
  • 编程新手真言......

    2009-04-02 20:25:15
    1.10 最小,最完美系统 39 1.11 操作系统与语言关系 41 1.12 虚拟机与语言 41 1.13 虚拟机与语言 42 1.14 调试器与汇编器 43 1.15 平台之GUI 45 1.16 界面本质应该是命令行功能支持下配置描述文件 45 1.17 ...
  • §6.2.7 步骤7:优化内存分配 88 §6.2.8 步骤8:优化I/O和物理结构 89 §6.2.9 步骤9:优化资源争用 89 §6.2.10 步骤10:优化所采用平台 89 §6.3 应用优化方法 90 §6.3.1 设定明确优化目标 90 §6.3.2 创建...
  • 实例071 利用安全数组借用内存的方法 实例072 利用指针实现数组插入 实例073 利用指针实现数组拆分 实例074 利用指针过滤数组重复数据 实例075 使用Split函数分隔明日公司网址 第4章 程序常用算法 4.1 ...
  • 千里马酒店前台管理系统V7使用手册

    热门讨论 2011-06-16 14:09:38
    硬件平台:建议服务器至少配1G内存(建议2G)、工作站至少配512M内存(建议1G)以获得较佳运行性能。 2.4 安装启动 千里马V7.2软件套装中包括安装光盘、使用手册。 2.4.1 客户端安装 运行安装光盘上SETUP...
  • 2.8.2 用于还原的内存缓冲区 48 2.8.3 RMAN内存利用:PGA与SGA 49 2.9 恢复目录 50 2.10 辅助数据库 51 2.11 版本兼容性 52 2.11.1 目标数据库与RMAN可执行文件 53 2.11.2 恢复目录数据库与恢复目录模式 53 ...
  • visio教程PDF

    热门讨论 2010-05-17 23:56:22
    1.3.2 选择适合自己需求的Visio版本 1.3.3 获得Visio支持方式 1.4 Visio功能 1.5 标准SmartShape模板 1.5.1 Block Diagrams 1.5.2 Flowcharts 1.5.3 Forms and Charts 1.5.4 Maps ...
  • -修正弹出对话框的宽度计算错误(会保持最小的状态)。 -增加新的皮肤Gray。 -为示例工程添加改变语言和皮肤的下拉列表。 -为PageContext增加静态函数Refresh,在切换语言和皮肤时使用。 +2009-12-01 v2.1.7...
  • 44_ElasticSearch 按每种颜色平均销售额降序排序 45_ElasticSearch 颜色+品牌下钻分析时按最深层metric进行排序 46_ElasticSearch 易并行聚合算法,三角选择原则,近似聚合算法 47_ElasticSearch ...

空空如也

空空如也

1 2
收藏数 35
精华内容 14
关键字:

内存需求最小的排序