10分钟梳理关系数据库基础知识(四):两阶段多路归并排序

每天10分钟,用去食堂吃饭的时间解决一个知识点。

重要性

今天来复习下两阶段多路归并排序。单独讲一次算法,是因为我觉得这个算法太重要了,不仅仅是对数据库而言。遇到一个不可能完成的大问题,将它划分成许多个小问题,分别求解,再将一系列小问题的解汇聚成大问题的解。这种”由大化小,分而治之“的思路,其实在计算机的许多领域都有闪耀。

问题

假定我们有一张表,10000000行吧,每行记录有100个Byte。这样,整张表粗略地估计为1GB。现在要求我们将这整张表的记录排个序。假设块的大小为4KB,也就是说,一个块中只能填40行记录,整张表占据250000个块。可供数据库排序使用的内存设为50MB,这样能放入内存的只有12800块。

如果所有记录都能放内存里面,那我们在学校里学的什么QuickSort MergeSort HeapSort都能排上用场了,想怎么排怎么排。但我们通过计算已经发现了,绝大多数记录都躺在磁盘上呢,这怎么办?

算法

解决思路就是我们(第一阶段)划分成一个个小部分,让小部分在内存中各自排好序,(第二阶段)再合并成大的结果。

具体来说,我们将250000个块中的12800个块装入内存,排好序,将结果写到磁盘上。这个整个一阶段要花多久呢?对于250000个块,每个块都要一次读一次写,这样就有500000次磁盘IO。假设每个块的读写为15毫秒(取个中间值),那么第一阶段总耗时就是125分钟。第二阶段中,我们将块读出,进行合并。但是我们换个角度,考查每个块的话,我们会发现,每个块都恰好是一次读一次写,同第一阶段一样。所以,整个过程的耗时可估算成250分钟。

块的大小

细心的同学应该已经发现了,在这个算法中,如果我们调大块的大小,那么磁盘IO次数就会减少。那么块是不是越大越好呢?当然不是。块太大的话磁盘上会有更多未利用的空间。当然,InnoDB中page的大小也是可以指定的,默认好像是16KB,具体就看DBA同学怎么定了。

原创声明,本文系作者授权云+社区-专栏发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏岑玉海

hbase源码系列(一)Balancer 负载均衡

  看源码很久了,终于开始动手写博客了,为什么是先写负载均衡呢,因为一个室友入职新公司了,然后他们遇到这方面的问题,某些机器的硬盘使用明显比别的机器要多,每次用...

2828
来自专栏mukekeheart的iOS之旅

MySQL学习笔记(一)

一、MySQL基础知识 MySQL 是一个真正的多用户、多线程 SQL 数据库服务器。 SQL(结构化查询语言)是世界上最流行的和标准化的数据库语言。MySQL...

2218
来自专栏Golang语言社区

山海传说ai 设计

一 城镇ai: 1.1 任务npc ai:当鼠标指向时,npc头顶会出现名字。并高亮显示npc模型。鼠标移开 后npc恢...

3398
来自专栏数据小魔方

美美的商务范儿——ggplot2蝴蝶图

一个小案例,使用ggplot2绘制蝴蝶图,在巩固温习条形图坐标轴翻转的同时,重新熟悉一下如何利用grid系统进行版式布局。 原图如下: ? 该图表思路很简单,...

3154
来自专栏逍遥剑客的游戏开发

PhysX学习笔记(3): 动力学(2) Actor

1262
来自专栏郭耀华‘s Blog

知乎问题代码

852
来自专栏Petrichor的专栏

tensorflow: tf.reshape探究

  给定一个tensor,这个操作会返回一个有着跟原tensor一样的值且经过shape重塑过的张量。

691
来自专栏知识分享

4-MSP430定时器_定时器中断

一开始没写好就上传了,,,,,,,,这次来个全的 自己学MSP430是为了写一篇关于PID的文章,需要430在proteus上做仿真,一则认为在自动控制算法上P...

3186
来自专栏PPV课数据科学社区

【学习】七天搞定SAS(一):数据的导入、数据结构

标题有些噱头,不过这里的重点是: speak SAS in 7days。也就是说,知识是现成的,我这里只是要学会如何讲这门语言,而不是如何边学SAS边学模型。顺...

2415
来自专栏用户2442861的专栏

腾讯2014校园招聘技术类笔试题详解

http://blog.csdn.net/silangquan/article/details/19977839

641

扫码关注云+社区