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

相关文章

来自专栏大数据钻研

真正的数据科学家 必备七大技术

如果你有志于做一个数据专家,你就应该保持一颗好奇心,总是不断探索,学习,问各种问题。在线入门教程和视频教程能帮你走出第一步,但是最好的方式就是通过熟悉各种已经在...

2806
来自专栏AI研习社

TensorFlow在工程项目中的应用 视频+文字转录(下)

本周四,雷锋网 AI 研习社邀请了跨国 IT 巨头 Thoughtworks 的资深数据架构师白发川,主讲线上公开课,为大家讲解 TensorFlow 在工程项...

3225
来自专栏机器之心

教程 | 一文入门Python数据分析库Pandas

选自Medium 作者:Ted Petrou 机器之心编译 参与:陈韵竹、李泽南 Pandas 通常用于快速简单的数据操作、聚合和可视化。在这篇文章中,我将概述...

3508
来自专栏理论坞

每个UI / UX设计师都需要知道心理学

心理学,在用户使用APP时扮演着重要角色,对于APP的用户体验有很大的影响。通过心理学,了解到我们的设计如何被用户使用,得到反馈,从而进行调整,以便我们的APP...

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

254页教程《Writing Code for NLP Research》

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

1522
来自专栏星流全栈

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

1824
来自专栏专知

【EMNLP2018干货】254 页《为NLP研究写出好代码》教程

【导读】现代的NLP研究工作都是需要编写代码。 良好的代码可以实现快速的原型设计,简单的代码调试,实验的可控性和可视化,帮助研究人员快速准确地了解

1304
来自专栏机器人网

【回顾】2017年最受欢迎的十大机器学习Python库

2017 年即将结束,又到了总结的时刻。本文作者把范围限定为机器学习,盘点了 2017 年以来最受欢迎的十大 Python 库;同时在这十个非常流行与强大的 P...

3158
来自专栏企鹅号快讯

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

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

2086
来自专栏机器之心

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

35614

扫码关注云+社区

领取腾讯云代金券