你好,我是王磊,你也可以叫我 Ivan。
今天,我们会继续学习查询场景中的处理技术。这一讲的关键词是“多表关联”,也就是数据库中常见的 Join 操作。无论是单体数据库还是分布式数据库,关联操作的语义始终没有变,一些经典算法也保持了很好的延续性。
关联算法作为一个稍微细节点的设计,在不同数据库中是有差异的,我们还是秉承课程的整体思路,不陷入具体的设置参数、指令等内容。这样安排的依据是,只要你掌握关联算法的基本原理,就能快速掌握具体数据库的实现了。同时,有了这些原理作为基础,你也能更容易地掌握分布式数据库的优化思路。
那么,我们先来看看这些经典的关联算法吧。
三类关联算法
常见的关联算法有三大类,分别是嵌套循环(Nested Loop Join)、排序归并(Sort-Merge Join)和哈希(Hash Join)。
嵌套循环连接算法
所有的嵌套循环算法都由内外两个循环构成,分别从两张表中顺序取数据。其中,外层循环表称为外表(Outer 表),内层循环表则称为内表(Inner 表)。因为这个算法的过程是由遍历 Outer 表开始,所以 Outer 表也称为驱动表。在最终得到的结果集中,记录的排列顺序与 Outer 表的记录顺序是一致的。