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 条评论
登录 后参与评论

相关文章

来自专栏机器学习算法与Python学习

254页教程《Writing Code for NLP Research》

EMNLP2018 254 页的《为NLP研究写出好代码》(Writing Code for NLP Research)的教程会给出答案。

862
来自专栏跨界架构师

软件开发中会用到的图

  大家应该在从事软件开发领域工作时间有一段时间之后,就开始有画图的意识,不管是懵懂的学别人还是想更好的让其它人理解自己的一个观点。所谓“一图胜千言”,我们身处...

1102
来自专栏专知

【书籍】深度学习框架:PyTorch入门与实践(附代码)

【导读】2016年是属于TensorFlow的一年,凭借谷歌的大力推广,TensorFlow占据了各大媒体的头条。2017年年初,PyTorch的横空出世吸引了...

9846
来自专栏企鹅号快讯

数据专家必知必会的 7款Python 工具

英文:Dynelle Abeyta译文:oschina www.oschina.net/translate/seven-python-tools-all-dat...

1986
来自专栏xingoo, 一个梦想做发明家的程序员

JS面向对象概述

这部分内容还是比较难理解的,像借用构造函数这种方法,实际工作中还是很常见的,不过对于后面的寄生理解还有点困难,只能慢慢学习了。 思维导图 ?

1995
来自专栏ThoughtWorks

DDD实战篇:分层架构的代码结构

不同于其它的架构方法,领域驱动设计DDD(Domain Driven Design)提出了从业务设计到代码实现一致性的要求,不再对分析模型和实现模型进行区分。也...

2854
来自专栏机器之心

从Pipenv到PyTorch,盘点2017年最受欢迎的十大机器学习Python库

33214
来自专栏数据科学与人工智能

推荐系统设计方法论

一、前言 结合目前已存在的商品推荐设计(如淘宝、京东等),推荐系统主要包含系统推荐和个性化推荐两个模块。 系统推荐: 根据大众行为的推荐引擎,对每个用户都给出同...

3698
来自专栏summer it专栏

大数据

5V特点(IBM提出):Volume(大量)、Velocity(高速)、Variety(多样)、Value(价值)、Veracity(真实性)。

2091
来自专栏星流全栈

【两分钟论文#161】AI创建用户界面,前端将失业?神器pix2code!

1564

扫码关注云+社区