阿里面试题亿级表合并引发的思考之 SQL Bloom Filter(一）.docx

阿里面试题亿级表合并引发的思考之 SQL Bloom Filter(一）很久之前，我写了一次亲身面试经历，在面试阿里的时候，有一题引起了我的思考，详情看这里：回忆当年阿里的一道 SQL 面试题，亿级表合并当时获得了很多读者朋友的反馈，大家兴趣盎然，回答都很详细，看得出来都很用心。包括知乎以及 CSDN 上的反应都很强烈。各自对数据库原理的理解不同，因此解法也都各异。有一位朋友的解法引起了我相当大的兴趣，且不说最终解法是否正确，单看他的思路就很奇特，我贴出来大家一起分析：这位朋友提到的 IBLT，是个比较新的数据结构，始创于2011年，主要应用场景来自于区块链共识算法。更深入的不在这里讨论，涉及区块链或者比特币的事情，暂时回避。有兴趣的朋友可以看下面的文章：https:/gist.github.com/gavinandresen/e20c3b5a1d4b97f79ac2Set reconciliation means finding the difference between two sets of data.Invertible Bloom Lookup Tables (IBLTs) are a new (described in 2011) data structure that can be used to solve the set reconciliation problem.https:/gist.github.com/gavinandresen/e20c3b5a1d4b97f79ac2随着深入挖掘下去，IBLT 引出来一个基础概念，就是布隆过滤器(Bloom Filter)，当然如果是科班的同学，对布隆肯定很熟悉。它的原理是这样的：首先，使用位数组，有向的记录每个元素的hash值位置：从左往右，以0-7记录每个比特（bit）的位置，每个比特位置可以存储0或者1，有1的地方代表了某个值可能出现，这个值究竟有多少个1组成，分布在哪些位置，都是由hash函数决定。第二要素，hash 函数比如我使用简单的取模函数，将每个字母的ASCII码值取模作为hash值，存到这位数组中，可以得到这样的结果：hash函数我们采用 T-SQL来写：CREATE FUNCTION dbo.fnHashByNine( Number Int ) RETURNS int AS BEGIN RETURN ( SELECT Number % 9 ) END GO取样字母的ASCII码HASH值求法： SELECT Name ,ASCII(Name) AS AsciiMark ,dbo.fnHashByNine(ASCII(Name) AS Remainder FROM ( SELECT DISTINCT LEFT(Name,1)AS Name FROM sys.objects ) RSL ORDER BY 2 ASC 最终排列到位数组，就成了刚才的那图：第三要素，匹配输入的字母：假设我们要判断 s(小写）是否在当前的集合中时, 首先求其 ASCII码，是 102， 取模后hash值为 7,此时 7 个位置，正好是空着，那意味着s不在此位数组中。众所周知，数据下标访问元素，时间复杂度为O(1)，时间恒定。聪明如你肯定会想到，如果能将这种方法用在判断两个集合中数据重合的可能性，那速度将会超快。是的，真如你所愿，各种数据库都实现了这类算法。我们将一一将其拨开来讲，这是第一篇。猜你喜欢：本周阶段性的收获颇丰，我满意了本号精华合集