这是这个系列的第五期，本期到了SQL 执行计划中经常会出现的两个熟悉的面庞， hash-base sort-Merge ，当然还有nested loops ,顺便这期还的说说索引，其中包含b-tree 索引以及bitmaps 数据结构，所以这期东西是异常混乱的。跟好了，别掉队哦
首先还是从我们熟悉的 b-tree 说起，这个数据结构组成的方式是每种数据库都支持的快速查找数据的存储结构，并为之在他的基础上建立的算法，这样的组合我们称之为B+TREE 索引。 所以一个索引是由数据结构和再次基础之上的算法组成的。
索引的成因其实主要还是因为数据量大，造成的数据查找定位的麻烦，所以索引的目的就是为了更快的获得数据准备的。那么会有一个问题，我先提出来，为什么是 B+TREE ，为什么B+TREE 是我们最常见的索引的类型，而不是别的，不是BRIN, 不是 GIST ,GIN 。
个人看法：一个最简单的数据结构，配合一个简单的算法，以及更快能估算出计算成本的方案，是一个应该被POP的方法，B+TREE 就是。 为了估计b树搜索的代价，我们需要计算深度。如果每个块包含f个指针，那么每一层的块数量是前一层的f倍。因此，包含N条记录的树的深度为log N / log f。算法简单，数据存储只需要改变后的类二叉树的存储结构，所以并不是别的索引类型不好，而是别的成本相对B+TREE “贵”，而最常用的使用场景B+TREE 也有很好的适应性。
这里B+TREE 本身包含三个点组成，1 根节点 2 叶子节点 3 指针 ，通过根节点将数据的范围进行划分，通过少量的判断查询方式就能快速定位到具体ROW 存在的PAGE ，然后在对PAGE中的数据进行search，提取具体使用的数据，所以B+TREE 对于顺序，范围提取也是长项。
简单的说完B+TREE ，下面的说说商业数据库常见的一种数据结构，BITMAPS，你可以在ORACLE ,SQL SERVER ，PG 等数据库经常看到BITMAPS , 说完BTREE，实际上BITMAPS 本身也是一种索引，一种数据结构，也是一种符合这样数据存储结构下的算法。一个数据块是8KB， BITMAPS 就是表达在两个表进行数据对比的过程中，那些数据块都包含所需要的数据，以位图的方式表达出来. 对于求多个条件的等值计算，也是一个好的方法，通过逻辑 and 操作，可以快速的通过少量的位图块计算出需要的数据行的位置。
位图方式的好处，主要体现在，查询中节省时间，减少在查询中的数据存储在大量的计算中对CPU的计算要求不高，并且可以有效的利用并行的方式进行计算。
位图方式的几个缺点也显而易见，1 对于频繁数据更新的表，BITMAPS维护的数据会被经常改变，修改BITMAPS的数据结构的数据难度比B+TREE 高， 同时对于采用BITMAPS的数据的采样率有一定要求，一定是查找的数据占整体数据行的少数，如果查找数据的行本身就占表数据量行的50%, 那么比对成本，要高于 TABLE SCAN 的成本。
下面就到标题中的下一个议题，nested loops , hash base, sort-merge 这三个2个表结合时的处理方法。
1 Nested Loops
Nested loops 是两个表进行关联关系最简单的算法，通过条件匹配，将两个表分为驱动表和搜索表，最终通过对搜索表的逐行比对，找到两个表中互相匹配的数据。算法很简单，但随着驱动表的加大，效率是根据表的大小成倍的性降低。
rows(R) * rows(S)
FOR row1 IN table1 LOOP
FOR row2 IN table2 LOOP
IF match(row1,row2) THEN
INSERT output row
END IF
END LOOP
END LOOP
2 Hash-based
基于上面的Nested loop 的性能问题，针对与表之间的关系有了新的方式进行数据的过滤，hash base ,hash join , 这个方法是将其中一个表中的关联的值通过hash 算法的方式将计算好的值放置到buckets （桶）中，将另一个表的对应的值发送到这个桶中，进行类nested loop 的对比，并发现匹配值，最终定位匹配的记录。
这个算法显然比NESTED LOOP 效率要高，对比是以hash buckets 的方式，而不是ONE BY ONE 的方式， 其中的cost 以 两个表的行数以及连接属性来决定，这里POSTGRESQL 采用的是 BLOOM 过滤器来操作的比对，这比在桶中使用nested loop的方式要更快
cost(hash,R,S)=size(R)+size(S)+size(R)*size(S)/size(JA)
HASH BASE 的方式也会受制于表的大小以及这些HASH 的数据是否可以直接存储在内存中，如果这些HASH 的值无法存在内存中，则效率会大大的降低。
3 Sort - Merge
Sort Merge 的方法是通过对需要连接的两个表的属性数据进行排序，获得两个表的顺序的数据，然后根据两个表的顺序性的数据笛卡尔积，在比对的过程中，凡是具有相同值的两个行是不会在出现笛卡尔积的结果中的，则最终那些不在输出中的行就是我们要的结果。
成本主要在两个表进行排序的过程，如果对比的两个列存在索引，这个sort 的过程就不会再次建立。
Size(R)*log(size(R)) + size(s)*log(size(S))
以上的几种多表的连接算法，中每个都与行的数据量有关，无论哪种算法对于大表和大表的关联都不会一件轻松的事情，所以两个表的关联在设计中尽量保证不要两个都是大表。
