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

相关文章

来自专栏顾宇的研习笔记

用操作系统课的知识解决自助餐排队问题背景 总结——如何对系统进行优化

这是在北京刚刚结束的2016年的第11届ThoughtWorks China AwayDay上发生的一件事:

602
来自专栏魏艾斯博客www.vpsss.net

搬瓦工 CN2 GT 年付 28 美元方案补货 洛杉矶 DC3/DC8 机房

1004
来自专栏腾讯云数据库(TencentDB)

腾讯自研新一代企业级云数据库CynosDB,打破安迪-比尔定律,释放硬件红利!

CynosDB是腾讯云自研的新一代高性能高可用的企业级分布式云数据库。融合了传统数据库、云计算与新硬件的优势,100%兼容开源数据库,百万级QPS的高吞吐,不限...

2.6K7
来自专栏ImportSource

异地双活实践笔记

最近恰好在搞异地双活,以下是一个梳理: 基本概念 1、异地容灾。这仅仅是一个冷备的概念。也就是在平时正常的时候,另外一个机房只是当做备份。 2、异地双(多)活...

1.4K7
来自专栏跨界架构师

如何一步一步用DDD设计一个电商网站(二)—— 项目架构

    上一篇我们讲了DDD的核心概念(附上链接),并且设计了我们的上下文映射图,那么接下来就准备开始立项了,本篇文章的部分知识点可能对一部分人来说比较基础,可...

971
来自专栏Spark学习技巧

HBase在滴滴出行的应用场景和最佳实践

本文主要介绍HBase在滴滴内部的一些典型使用场景,如何设计整个业务数据流,让平台开发者与用户建立清晰、明确、良好的合作关系 背景 对接业务类型 HBase是建...

2728
来自专栏我是攻城师

Hadoop/Spark生态圈里的新气象

3395
来自专栏Java技术

记录一次壮烈牺牲的阿里巴巴面试!

今天本是一个阳光明媚,鸟语花香的日子。于是我决定在逛街中感受春日的阳光~结果晚上七点的时候,蚂蚁金服后端大佬来了电话,要进行一轮的技术面试。我一脸黑人问号???...

551
来自专栏编程一生

战狼:业务高速增长下,如何保证系统的稳定性和高可用?

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

漫谈Java IO之基础篇

Java的网络编程如果不是专门搞服务器性能开发或者消息分发,几乎可能涉及不到。但是它却是面试找工作必问的一个知识点,涵盖的知识体系也非常广泛,从Java底层I...

3256

扫码关注云+社区