阿里面试题亿级表合并引发的思考之 SQL Bloom Filter(一).docx
6页1、阿里面试题亿级表合并引发的思考之 SQL Bloom Filter(一)很久之前,我写了一次亲身面试经历,在面试阿里的时候,有一题引起了我的思考,详情看这里:回忆当年阿里的一道 SQL 面试题,亿级表合并当时获得了很多读者朋友的反馈,大家兴趣盎然,回答都很详细,看得出来都很用心。包括知乎以及 CSDN 上的反应都很强烈。各自对数据库原理的理解不同,因此解法也都各异。有一位朋友的解法引起了我相当大的兴趣,且不说最终解法是否正确,单看他的思路就很奇特,我贴出来大家一起分析:这位朋友提到的 IBLT,是个比较新的数据结构,始创于2011年,主要应用场景来自于区块链共识算法。更深入的不在这里讨论,涉及区块链或者比特币的事情,暂时回避。有兴趣的朋友可以看下面的文章:https:/ reconciliation means finding the difference between two sets of data.Invertible Bloom Lookup Tables (IBLTs) are a new (described in 2011) data structure that ca
2、n be used to solve the set reconciliation problem.https:/ 引出来一个基础概念,就是布隆过滤器(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),时间恒定。聪明如你肯定会想到,如果能将这种方法用在判断两个集合中数据重合的可能性,那速度将会超快。是的,真如你所愿,各种数据库都实现了这类算法。我们将一一将其拨开来讲,这是第一篇。猜你喜欢:本周阶段性的收获颇丰,我满意了本号精华合集
《阿里面试题亿级表合并引发的思考之 SQL Bloom Filter(一).docx》由会员A***分享,可在线阅读,更多相关《阿里面试题亿级表合并引发的思考之 SQL Bloom Filter(一).docx》请在金锄头文库上搜索。
SAP UI5应用里类型为Edm.DateTime的日期控件设计原理.docx
SAP UI5 Web Component for React的图标和图片处理.docx
SAP UI5应用和Hybris Commerce的国际化(internationalization)支持.docx
SAP UI5 Web Component里最简单的React列表控件的用法.docx
SAP UI5 Connection manager.docx
SAP UI5 jQuery.sap.setObject.docx
SAP WebClient UI drop down list(下拉列表)的一个故障和解决方法.docx
SAP UI5 GM6 require sap.ui.core.Core.docx
SAP UI5应用如果遇到数据绑定问题时应该如何自己定位问题?.docx
SAP云平台上的Mendix服务 - 如何注册帐号.docx
SAP Odata filter的语法.docx
SAP UI5和React的页面渲染性能比较.docx
SAP UI5 setModel of scFld Controller.docx
SAP Netweaver后台作业的几种状态.docx
SAP UI5 Opportunity popup.docx
SDL_FillRect函数.docx
SDL_Rect结构.docx
SAP UI5 component container initialized in index html.docx
SAP UI5应用里的列表处理.docx
SAP UI5 ResponsiveGridLayout.docx
2024-01-15 24页
2024-01-15 15页
2024-01-08 89页
2024-01-08 72页
2023-08-31 3页
2023-08-31 2页
2023-07-10 3页
2023-07-10 3页
2023-07-10 3页
2023-07-10 2页