第9讲逻辑设计与物理

将概念结构转化为关系、网状、层次或其他数据结构将得到的关系、网状、层次模型向特定BS支持下的数据模型转换 1班学班学 n课m1教n课m1教n1教教科 （关系的属性：实体型的属关系的键：实体型的 年级，平均成绩 关系的键：各实体键的组 关系的键：n端实体的 （2）与n合并后关系的属性：在n端关系中加入1端关系的键和联系本身的属→可以减少系统中的关系个数，一般情况下更倾向于采用 关系的键：各实体键的组 籍贯（学号，籍贯学生（学号 ，出生日期，所在系，年级班级号，平均成绩学生（学号 ，出生日期，籍贯，所在系年级，班级号，平均成绩 1班学班学 n课m1教n课m1教n1教教科 [1:n关系] 数据模型的优 辅助材 Solutions–A

Databases.(数据库设 ，何玉洁翻译，2nd机械工 丁宝

数据库的物理设 数据库实施、运行 概什么是数据库的物理设 Databasesystemsalreadydothis…,Butitisimportanttounderstandhowtheywork–thetechniquesarealsousefulforotherapplications!'sLinuxclustercurrentlyprocessesover150millionqueriesperday,searchingamulti-bytewebindexforeveryquerywithanaverageresponsetimeoflessthan¼secondwithnear-100%uptime.TraditionalrelationaldatabasesarenotsuitableKnowledgeofdatabasetechniquesrequiredtobuildcustom–Howtostoredata?Goal:efficiency,high-–Howtoefficientlyaccessdata?Goal:lowresponse

查询的关查询/连接条件所涉及的查询的投影属被更新的关每个关系上的更新操作条件所涉及的属修改操作要改变的属性

数据库的物理设 数据库实施、运行 概

例如 馆作

索引存取方法的选

(Dense

(Sparse 找到<K

；

→+（数据结构层面额外的空间开销

ExampleofaB+-treeB+-treeforaccountfile(n=n:每个节点pointer个

B+TreeAB+treeisarootedtreesatisfyingthefollowingAllpathsfromroottoleafareofthesamelength– abalancedMinimum50%occupancy(exceptfor-- (nNon-

<=occupancy<=n-<=occupancy<=nisfixedforagivenSpecialIftherootisnotaleaf,ithasatleast2Iftherootisaleaf(thatis,therearenoothernodesintree),itcanhavebetween0and(n–1)

B+TreeNodeKiarethesearch-keyPiarepointerstochildren(fornon-leafnodes)orpointerstorecords(forleafnodes).Thesearch-keysinanodeareK1<K2<K3<...<

Foranon-leafnodewithmAllthesearch-keysinthesubtreetowhichpointsarelessthanFor2in–1,allthesearch-keysinthesubtreetowhichPipointshavevaluesgreaterthanorequaltoKi–1andlessthanKiAllthesearch-keysinthesubtreetowhichpointshavevaluesgreaterthanorequalto

LeafNodesinB+-PropertiesofaleafFori=1,2,...,n–1,pointerPieitherpointstoafilerecordwithsearch-keyvalueKi,eachrecordhavingsearch-keyvalueKi.Onlyneedbucketstructureifsearch-keydoesnotformaprimaryIfLi,Ljareleafnodesandi<j,Li’ssearch-keyvaluesarelessLj’ssearch-keyPnpointstonextleafnodeinsearch-key

ExampleofaB+-treeB+-treeforaccountfile(n=n:每个节点pointer个

ExampleofB+TreeSearch-keysinanodearePointerstonodesor

SearchoveraB+Searchbeginsatroot,andkeycomparisonsdirectittoaleafSearchfor5*,15*,alldataentries>=24*

实际应用中的B+Typicaln:198.Typicalfill-factor:averagefanout=198*.67=TypicalHeight4:1334=312,900,700Height3:1333=2,352,637CanoftenholdtoplevelsinbufferLevel1=1page=8Level2=133pages=1Level3=17,689pages=133

B+Tree节点间由指针连接，’logically’ closeblocksneednotbe‘physically’close Tree包含相对较小数目的层次（

B+Tree

UpdatesonB+Trees:FindtheleafnodeLinwhichthesearch-keyvaluewouldIfthesearch-keyvalueisalreadythereintheleafnode,recordisaddedtofileandifnecessaryapointerisinsertedintothebucket.Ifthesearch-keyvalueisnotthere,thenaddtherecordtotheIfthereisroomintheleafnode,insert(key-value,pointer)pairtheleafOtherwise,mustsplitL(intoLandredistributeentriesevenly,copyupmiddleInsertindexpointingtoLnewintoparentofThiscanhappenrecursively--tosplitindexnode,pushupSplitsgrowtreerootsplitincreasestree

Inserting8*intoB+

After8*

DeletingaDataEntryfromaB+Startatroot,findleafLwhereentryRemovetheIfLisatleasthalf-full,IfLhasonly(n-1)/2withsameparentasIfre-distributionfails,mergeLandIfmergeoccurred,mustdeleteentry(pointingLorsibling)fromparentofMergecouldpropagatetoroot,

Merge…Depth3->2…

(B+tree语法：CREATEINDEXind_nameONtable_name(col_name)

B+TreeB+Tree是所有DBMS中使用最为广泛的索引方法，由于其广泛适用性；因此B+Tree为什么使用B+TreeB+Tree动态结→优雅的插入/删除操值

ExampleofHashFile对于account关系文件branch_nameThereThereare10ThebinaryrepresentationoftheithcharacteristobetheintegerThehashfunctionreturnsthesumoftherepresentationsofthecharactersmoduloE.g.h(Perryridge)= h(RoundHill)= h(Brighton)=ExampleofHashFileHash的Hh函数将检索关键字映射至一个Buct;理想的Hash函uniform,i.e.,eachbucketisassignedthesamenumberofsearch-keyvaluesfromthesetofallpossiblevalues.random,soeachbucketwillhavethesamenumberofrecordsassignedtoitirrespectiveoftheactualdistributionofsearch-keyvaluesinthefile.典型的Hh函数使用基于检索关键字内部二进制值的

数据库的物理设 数据库实施、运行 概

确定数据库物 结构的内数据的存放位置 结

例：消除一切冗余数据虽能够节

SpeedCostSize

结构(续

Primarystorage(Offlinestorage，

50K-100Ktracks TrackdividedintoAsectoristhesmallestunitofdatathatcanbereadorSectorsizetypically512Typicalsect