数据结构翻译.docx

数据结构翻译.docx

《数据结构翻译.docx》由会员分享，可在线阅读，更多相关《数据结构翻译.docx（29页珍藏版）》请在冰点文库上搜索。

数据结构翻译

（a,b）树和B树

Adifferentmethodtokeeptheheightofthetreessmallistoallowtreenodesofhigherdegree.ThisideawasintroducedasB-treesbyBayerandMcCreight（1972）andturnedouttobeveryfruitful.Itwasoriginallyintendedasexternalmemorydatastructure,butwewillseeinSection3.4thatithasinterestingusesalsoasnormalmainmemorydatastructure.Thecharacteristicofexternalmemoryisthataccesstoitisveryslow,comparedtomainmemory,andisdoneinblocks,unitsmuchlargerthansinglemainmemorylocations,whicharesimultaneouslytransferredintomainmemory.Inthe1970s,computerswerestillverymemorylimitedbutusuallyalreadyhadalargeexternalmemory,sothatitwasanecessaryconsiderationhowastructureoperateswhenalargepartofitisnotinmainmemory,butonexternalmemory.Thissituationisnowless

important,butitisstillrelevantfordatabaseapplications,whereB-treevariantsarestillmuchusedasindexstructures。

不同的方法保持树的高度是允许有更高度的树节点。

这个想法是在1972由BayerandMcCreight在B树中介绍的并且证明是非常有成果的。

它原本是外部存储数据结构,但我们在3.4节中看到的,它也被广泛的使用作为主存储数据结构。

外部存储器的特点是与主存储器相比，访问非常慢并且在块中被使用。

外存单元远远大于单一主存单元，同时转移到主内存。

在19世纪70年代,计算机内存仍非常有限,但通常已经有了一个很大的外部存储器。

所以这是一个必要的考虑，一个结构当它很大的一部分,不是在主内存,而是在外部存储器如何运作。

这种情况现在不那么重要,但它仍然和数据库应用程序相关，B-树变体仍多用作索引结构。

Theproblemwithnormalbinarysearchtreesasexternalmemorystructureisthateachtreenodecouldbeinadifferentexternalmemoryblock,whichbecomesknownonlywhenthepreviousblockhasbeenretrievedfromtheexternalmemory.Sowemightneedasmanyexternalmemoryblockaccessesastheheightofthetree,whichismorethanlog2（n）,andwouldbeinterestedineachoftheseblocks,whicharelargeenoughtoholdmanynodes,injustasinglenode.TheideaofB-treesistotakeeachblockasasinglenodeofhighdegree.Intheoriginalversion,eachnodehasdegreebetweenaand2a−1,

whereaischosenaslargeaspossibleundertheconditionthatablockmusthaveroomfor2a−1pointersandkeys.Thenbalancewasmaintainedbythecriterionthatallleavesshouldbeatthesamedepth.

普通二进制搜索树作为外部内存结构的问题是每个树节点可以在不同外部内存块,只有前面的块已经从外部存储器中检索时它成为已知。

所以我们需要尽可能多的外部内存块访问树的高度,这个高度大于log2（n）并且这些块可以容纳足够多的节点，仅仅在一个节点。

B树的想法是把每一块作为一个节点的高度。

在最初的版本中，每个节点的度是在a和2a−1之间，a尽最大的可能在块必须有空间容纳2a-1个指针和键的条件下选择。

然后保持平衡的标准,所有的树叶都应该在同一深度。

Thedegreeintervalato2a−1isthesmallestintervalforwhichtherebalancingalgorithmfromBayerandMcCreight（1972）works.Becauseeachblockhasroomforatmost2a−1elementsandisatleasthalffullthisway,itsoundedlikeagoodchoicetooptimizethespaceutilization.ButthenitwasdiscoveredbyHuddlestonandMehlhorn（1982）andindependentlybyMaier

andSalveter（1981）thatchoosingtheintervalabitlargermakesanimportantdifferencefortherebalancingalgorithm;ifoneallowsnodedegreesfromatobforb≥2a,thenrebalancingchangesonlyamortizedO

（1）blocks,whereas

Forb=2a−1,theoriginalchoice,

（logn）blockchangescanbenecessary.Foramainmemorydatastructure,thenumberofchangesinrebalancingmakeslittledifference,althoughithasbeenstudiedinmanypapers;butforanexternalmemorystructureitisessentialbecauseallchangedblockshavetobewrittenagaintotheexternalmemorydevice.Sothesetrees,knownas（a,b）-trees,arethemethodofchoice.

从BayerandMcCreight提出的平衡算法中，度的间隔在a到2a-1之间是最小的间隔。

因为每一块的空间最多是2a-1个元素，并且至少有一半是符合这种方式的。

这听起来像一个不错的选择来优化空间利用率。

但是后来被Huddleston和Mehlhorn发现，并且独立于Maier

和Salveter选择的间隔，这个间隔有点大且和平衡算法大大不同。

如果允许节点的度从a到b，且b≥2a-1然后平衡改变复杂度为O

（1）的块。

而对于b=2a−1,最初的选择是O（logn）的块的改变是必要的。

对于主内存数据结构,平衡的数量变化不大,虽然它已经在许多论文中研究;但对于外部内存结构至关重要,因为所有改变块必须重写到外部存储设备。

所以这些树,称为（a,b）树,是选择的方法。

An（a,b）-treeisanonbinarysearchtreeinwhichallleaveshavethesamedepth;eachnonrootnodehasdegreebetweenaandb,withb≥2a,andtheroothasdegreeatmostbandatleast2（unlessthetreeisemptyorhasonlyoneleaf）.An（a,b）-treehasnecessarilysmallheight.

一棵（a,b）树是一棵非二叉搜索树，所以的叶子都有相同的深度。

每个非根节点的度都在a，b之间，且b≥2a，根节点的度最大是b，最小是2（除非树是空的或者只有一个节点）。

一棵（a,b）树有一定较小的高度。

Theorem.An（a,b）-treeofheighth≥1hasatleast2ah−1andatmostbhleaves.An（a,b）-treewithn≥2leaveshasheightatmost

。

Thisfollowsimmediatelyfromthedefinition.

定理：

（a,b）树的高度h≥1，则至少有2ah−1和至多bh个叶子。

（a,b）树有n≥2个叶子节点的高度至多是

。

下面马上从这个定义中给出证明。

Becausethesetreesarenotbinarysearchtrees,theydonotfallintheframeworkdescribedinChapter2,andwehavetodefinetheirstructureandourconventionsfortheirrepresentationinadditiontotherebalancingalgorithm.Anodehasthefollowingstructure:

由于这种树不是二叉搜索树，它们不符合第二章描述的结构，我们必须定义它们的结构和我们表示的约定除了平衡算法。

一个节点具有以下结构:

typedefstructtr_n_t{intdegree;

intheight;

key_tkey[B];

structtr_n_t*next[B];

/*possiblyotherinformation*/

}tree_node_t;

Wedescribethe（a,b）-treehereasamainmemorystructure;foranexternalmemoryversion,wewouldneedtoestablishacorrespondencebetweenthemainmemorynodesandtheexternalmemoryblocks,andwouldneedfunctionstorecoveranodefromexternalmemoryandwriteitback.

我们这里描述的（a,b）树是作为一种主存储结构，对于外存储器版本，我们需要建立一个在主存节点和外存块的通信，并且需要从外存恢复一个节点且写回的功能。

Thenodestructurecontainsthedegreeofthenode,whichisatmostB,andspaceforuptoBoutgoingedges.ItalsocontainsspaceforBkeyvalues.Usuallyweneedonlyonekeyvaluelessthanthedegreetoseparatetheoutgoingedges,butinthenodeatthelowestlevel,weavoidhavingseparateleafnodesandinsteadplacetheobjectreferencestogetherwiththeirassociatedkeyvaluesinthatnode.Weneedaconventiontoidentifythenodesonthelowestlevel;forthisreasonweincludetheheightofthenodeabovethelowestlevelinthenode.

节点的结构包含了节点的度，这些度最多是B，B的空间超出边界。

它也包含了B的空间的关键字。

通常我们需要一个小于度的关键字去分离超出的边界。

但是在最低水平的节点，我们避免单独的叶节点,而是一起引用对象相关节点的键值。

我们需要一个约定来确定节点的最低水平;因此我们包括节点的高度高于最低水平的节点高度。

Asinthecaseofbinarysearchtrees,weassociatewitheachnodeahalfopenintervalofthepossiblekeyvaluesthatcanbereachedthroughthatnodeorpointer.If*nisanodewithassociatedinterval[a,b[,thentheassociatedintervalsofthenodesreferencedtobynextpointersareasfollows:

在二叉搜索树的情况下，我们结合每个节点可能键值的半开放间隔，这些键值可以通过节点或指针得到。

如果*n是一个节点相关联的区间[a,b[,那么节点的相关间隔通过下一个指针引用如下:

{forn->next[0],theinterval[a,n->key[1][;

一棵（4，8）树

{forn->next[i],with1≤i≤n->degree−2,theinterval

[n->key[i],n->key[i+1][;and

{forn->next[n->degree-1]theinterval

[n->key[n->degree-1],b[.

Thenthefindoperationlooksasfollows:

然后查找操作看起来如下：

object_t*find（tree_node_t*tree,

key_tquery_key）

{tree_node_t*current_node;

object_t*object;

current_node=tree;

while（current_node->height>=0）

{intlower,upper;

/*binarysearchamongkeys*/

lower=0;upper=current_node->degree;

while（upper>lower+1）

{if（query_key<

current_node->key[（upper+lower）/2]）

upper=（upper+lower）/2;

3.3（a,b）-andB-Trees75

else

lower=（upper+lower）/2;

}

if（current_node->height>0）

current_node=

current_node->next[lower];

else

{/*blockofheight0,containsthe

objectpointers*/

if（current_node->key[lower]==

query_key）

object=（object_t*）

current_node->next[lower];

else

object=NULL;

return（object）;

}

}

}

Byperformingbinarysearchonthekeyswithinthenode,thefindoperationisasfastasafindinabinarytree.

通过查找二叉搜索树节点内的关键字，这个查找操作和查找二叉树一样快。

Nowwefinallyhavetodescribetheinsertanddeleteoperationsandtherebalancingthatkeepsthestructureofthe（a,b）-tree.Insertanddeletebeginstraightforwardasinthebinarysearch-treecase:

firstonegoesdowninthetreetofindtheplacewhereanewleafshouldbeinsertedoranoldoneshouldbedeleted.Thisisinanodeofheight0.Ifthereisstillroominthenodeforthenewleaforafterthedeletiontheleafstillcontainsatleastaobjects,thereisnoproblem,butthenodecouldoverflowduringaninsertionorbecomeunderfullduringadeletion.Inthesecaseswehavetochangesomethinginthestructureofthetreeandpossiblypropagatethestructureupward.Therestructuringrulesforthesesituationsareasfollows:

现在我们终于有了描述插入和删除操作和保持（a,b）树结构重新平衡，插入和删除直接在二叉搜索树的情况下：

在树中跌落第一个节点找到一个地方，新的叶子节点插入或者旧的节点应该删除。

这个节点的高度为0.如果该节点对新的叶子节点和之后删除的叶子节点还有空间仍然包含至少一个对象，这是没有问题的。

但是这个节点在插入的时候溢出或者在删除的时候中变成满树。

在这种情况下我们必须改变一些树的结构和可能向上传播的结构。

这些情况的重组规则如下:

{Foraninsertion:

ifthecurrentnodeoverflows

a.Ifthecurrentnodeistheroot,createtwonewnodes,copyintoeachhalftherootentries,andputintotherootjustpointerstothesetwonewnodestogetherwiththekeythatseparatesthem.Increasetheheightoftherootby1.

b.Elsecreateanewnodeandmovehalftheentriesfromtheoverflowingnodetothenewnode.Theninsertthepointertothenewnodeintotheupperneighbor.

Thecasebisknownas“splitting.”

对于插入操作：

如果当前的节点溢出

a.如果当前的节点是根节点，创建两个节点，复制到每个半根的目录下，并且把根节点指向这两个新的节点，这两个节点是通过关键字区分开来的，然后根节点的高度增加1.

b.否则创建一个新的节点，从溢出的节点的半个条目移动到新节点上，然后插入新节点的指针指向它的父节点。

b这种情况叫做“分割”。

{Foradeletion:

ifthecurrentnodebecomesunderfull

a.Ifthecurrentnodeistheroot,itisunderfullifithasonlyoneremainingpointer.Copythecontentofthenodetowhichthepointerpointsintotherootnodeandreturnthenodetothesystem.

b.Elsefindtheblockofthesameheightthatimmediatelyprecedesorfollowsitinthekeyorderandhasthesameupperneighbor.Ifthatblockisnotalreadyalmostunderfull,moveakeyanditsassociatedpointerfromthatblockandcorrectthekeyvalueseparatingthesetwoblocksintheupperneighbor.

c.Elsecopyentriesofthecurrentnodeintothatalmostunderfullneighboringnodeofthesameheight,returnthecurrentnodetothesystem,anddeletethereferencetoitfromtheupperneighbor.

Thecasesbandcareknownas“sharing”and“joining,”

respectively.

对于删除操作，如果当前的节点变成未满节点。

a.如果当前的节点是根节点，如果它只有一个指针，那么它是满节点。

复制该节点的内容给它指向的根节点，并向系统返回该节点。

b.否则，找到相同高度的块，这些块在关键字的顺序上先于过等于该节点并且有相同的父节点。

如果这个块已经不是满的，然后从这