资源描述：
《kc第13讲-数据散列技术.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第13讲:(第12章)数据散列技术重庆大学计算机学院课程名称:数据库系统--------------------第13讲：数据散列技术项目驱动目标：如何实现基于散列的文件组织和索引：一、静态散列二、动态散列三、SQL中的索引定义主要讨论问题：什么是静态散列好的散列函数该是什么样什么是动态散列如何在动态散列中插入记录如何删除动态散列中的记录与静态散列相比,动态散列有特点顺序索引与散列的区别SQL中如何定义索引Exercise13StaticHashing(静态散列)Abucket(桶)isaunitofstoragecontainingoneormorere
2、cords(abucketistypicallyadiskblock).Inahashfileorganization(散列文件组织)weobtainthebucketofarecorddirectlyfromitssearch-keyvalueusingahashfunction(散列函数).Hashfunctionhisafunctionfromthesetofallsearch-keyvaluesKtothesetofallbucketaddressesB.Hashfunctionisusedtolocaterecordsforaccess,inserti
3、onaswellasdeletion.Recordswithdifferentsearch-keyvaluesmaybemappedtothesamebucket;thusentirebuckethastobesearchedsequentiallytolocatearecord.一静态散列1-1什么是静态散列？问题1答案1.1基本概念ExampleofHashFileOrganizationThereare10buckets,Thebinaryrepresentationoftheithcharacterisassumedtobetheintegeri.The
4、hashfunctionreturnsthesumofthebinaryrepresentationsofthecharactersmodulo10.E.g.h(Perryridge)=5h(RoundHill)=3h(Brighton)=3h(Mianus)=7Hashfileorganizationofaccountfile,usingdept_nameaskey2,18,9,7,8,20,15,14字母对应的数字编号2*317+18*316+9*315+7*314+8*313+20*312+15*311+14=71264679513(模10余数是3)放入
5、3号桶13,9,1,14,21,19((((13*31+9)*31+1)*31+14)*31+21)*31+19=380534567(模10余数是7)放入7号桶1.1基本概念HashFunctions(散列函数)Worsthashfunctionmapsallsearch-keyvaluestothesamebucket;thismakesaccesstimeproportionaltothenumberofsearch-keyvaluesinthefile.Anidealhashfunctionisuniform(均匀的),i.e.,eachbucketisa
6、ssignedthesamenumberofsearch-keyvaluesfromthesetofallpossiblevalues.(桶的尺寸一样大！)Anidealhashfunctionisrandom(随机的),soeachbucketwillhavethesamenumberofrecordsassignedtoitirrespectiveoftheactualdistributionofsearch-keyvaluesinthefile.(桶中放的记录一样多！)Typicalhashfunctionsperformcomputationonthei
7、nternalbinaryrepresentationofthesearch-key.Forexample,forastringsearch-key(如account的部门名),thebinaryrepresentationsofallthecharactersinthestringcouldbeaddedandthesummodulothenumberofbucketscouldbereturned..1-2好的散列函数该是什么样？1.1基本概念问题2答案ProblemsofBucketOverflows(溢出问题)Bucketoverflowcanoccur
8、becauseofIns
