亚洲国产区中文,国产精品91高清,亚洲精品中文字幕久久久久,亚洲欧美另类久久久精品能播放

概述

  B樹(shù) （Bayer & McCreight 1972） (order為5) （Knuth 1998）.

在B樹(shù)中，內(nèi)部（非葉子）節(jié)點(diǎn)可以擁有可變數(shù)量的子節(jié)點(diǎn)（數(shù)量范圍預(yù)先定義好）。當(dāng)數(shù)據(jù)被插入或從一個(gè)節(jié)點(diǎn)中移除，它的子節(jié)點(diǎn)數(shù)量發(fā)生變化。為了維持在預(yù)先設(shè)定的數(shù)量范圍內(nèi)，內(nèi)部節(jié)點(diǎn)可能會(huì)被連結(jié)或者分離。因?yàn)樽庸?jié)點(diǎn)數(shù)量有一定的允許范圍，所以B樹(shù)不需要像其他自平衡查找樹(shù)那樣頻繁地重新保持平衡，但是由于節(jié)點(diǎn)沒(méi)有被完全填充，可能浪費(fèi)了一些空間。子節(jié)點(diǎn)數(shù)量的上界和下界依特定的實(shí)現(xiàn)而設(shè)置。例如，在一個(gè)2-3 B樹(shù)（通常簡(jiǎn)稱(chēng)2-3樹(shù)），每一個(gè)內(nèi)部節(jié)點(diǎn)只能有2或3個(gè)子節(jié)點(diǎn)。

B樹(shù)中每一個(gè)內(nèi)部節(jié)點(diǎn)會(huì)包含一定數(shù)量的鍵值。通常，鍵值的數(shù)量被選定在 d {\displaystyle d} 和 2 d {\displaystyle 2d} 之間。在實(shí)際中，鍵值占用了節(jié)點(diǎn)中大部分的空間。因數(shù)2將保證節(jié)點(diǎn)可以被拆分或組合。如果一個(gè)內(nèi)部節(jié)點(diǎn)有 2 d {\displaystyle 2d} 個(gè)鍵值，那么添加一個(gè)鍵值給此節(jié)點(diǎn)的過(guò)程，將會(huì)拆分 2 d {\displaystyle 2d} 鍵值為2個(gè) d {\displaystyle d} 鍵值的節(jié)點(diǎn)，并把此鍵值添加給父節(jié)點(diǎn)。每一個(gè)拆分的節(jié)點(diǎn)需要最小數(shù)目的鍵值。相似地，如果一個(gè)內(nèi)部節(jié)點(diǎn)和他的鄰居兩者都有 d {\displaystyle d} 個(gè)鍵值，那么將通過(guò)它與鄰居的合并來(lái)刪除一個(gè)鍵值。刪除此鍵值將導(dǎo)致此節(jié)點(diǎn)擁有 d ? ? --> 1 {\displaystyle d-1} 個(gè)鍵值;與鄰居的合并則加上 d {\displaystyle d} 個(gè)鍵值，再加上從鄰居節(jié)點(diǎn)的父節(jié)點(diǎn)移來(lái)的一個(gè)鍵值。結(jié)果為完全填充的 2 d {\displaystyle 2d} 個(gè)鍵值。

一個(gè)節(jié)點(diǎn)的分支（或子節(jié)點(diǎn)）的數(shù)量會(huì)比存儲(chǔ)在節(jié)點(diǎn)內(nèi)部鍵值的數(shù)量大1。在2-3 B樹(shù)中，內(nèi)部節(jié)點(diǎn)將會(huì)存儲(chǔ)1個(gè)鍵值（帶有2個(gè)子節(jié)點(diǎn)）或2個(gè)鍵值（帶有3個(gè)子節(jié)點(diǎn)）。一個(gè)B樹(shù)有時(shí)會(huì)被描述為 ( d + 1 ) ? ? --> ( 2 d + 1 ) {\displaystyle (d+1)-(2d+1)} 或簡(jiǎn)單地使用最高分支 ( 2 d + 1 ) {\displaystyle (2d+1)} 。

一個(gè)Ｂ樹(shù)通過(guò)約束所有葉子節(jié)點(diǎn)在相同深度來(lái)保持平衡。深度在元素添加至樹(shù)的過(guò)程中緩慢增長(zhǎng)，而整體深度極少地增長(zhǎng)，并導(dǎo)致所有葉子節(jié)點(diǎn)與根節(jié)點(diǎn)距離加1。

在存取節(jié)點(diǎn)數(shù)據(jù)所耗時(shí)間遠(yuǎn)超過(guò)處理節(jié)點(diǎn)數(shù)據(jù)所耗時(shí)間的情況下，Ｂ樹(shù)在可選的實(shí)現(xiàn)中擁有很多優(yōu)勢(shì)，因?yàn)榇嫒」?jié)點(diǎn)的開(kāi)銷(xiāo)被分?jǐn)偟嚼飳庸?jié)點(diǎn)的多次操作上。這通常出現(xiàn)在當(dāng)節(jié)點(diǎn)存儲(chǔ)在二級(jí)存儲(chǔ)器如硬盤(pán)存儲(chǔ)器上。通過(guò)最大化內(nèi)部里層節(jié)點(diǎn)的子節(jié)點(diǎn)的數(shù)量，樹(shù)的高度減小，存取節(jié)點(diǎn)的開(kāi)銷(xiāo)被縮減。另外，重新平衡樹(shù)的動(dòng)作也更少出現(xiàn)。子節(jié)點(diǎn)的最大數(shù)量取決于，每個(gè)子節(jié)點(diǎn)必需存儲(chǔ)的信息量，和完整磁盤(pán)塊的大小或者二次存儲(chǔ)器中類(lèi)似的容量。雖然2-3 樹(shù)更易于解釋?zhuān)瑢?shí)際運(yùn)用中，Ｂ樹(shù)使用二級(jí)存儲(chǔ)器，需要要大量數(shù)目的子節(jié)點(diǎn)來(lái)提升效率。

變體

術(shù)語(yǔ)Ｂ樹(shù)可以指一個(gè)特定的方案，也可以指大體上一類(lèi)方案。狹義上，一個(gè)Ｂ樹(shù)在它內(nèi)部節(jié)點(diǎn)中存儲(chǔ)鍵值，但不需在葉子節(jié)點(diǎn)上存儲(chǔ)這些鍵值的記錄。大體上的一類(lèi)包含一些變體，如B+樹(shù)和Ｂ*樹(shù)。

在Ｂ+樹(shù)，這些鍵值的拷貝被存儲(chǔ)在內(nèi)部節(jié)點(diǎn)；鍵值和記錄存儲(chǔ)在葉子節(jié)點(diǎn)；另外，一個(gè)葉子節(jié)點(diǎn)可以包含一個(gè)指針，指向另一個(gè)葉子節(jié)點(diǎn)以加速順序存取。

B*樹(shù)分支出更多的內(nèi)部鄰居節(jié)點(diǎn)以保持內(nèi)部節(jié)點(diǎn)更密集地填充。此變體要求非根節(jié)點(diǎn)至少2/3填充，而不是1/2。為了維持這樣的結(jié)構(gòu)，當(dāng)一個(gè)節(jié)點(diǎn)填滿之后將不會(huì)再立即分割節(jié)點(diǎn)，而是將它的鍵值與下一個(gè)節(jié)點(diǎn)共享。當(dāng)兩個(gè)節(jié)點(diǎn)都填滿之后，分割成3個(gè)節(jié)點(diǎn)。

計(jì)數(shù)B樹(shù)存儲(chǔ)，每一樹(shù)都帶有一個(gè)指針和其指向子樹(shù)的節(jié)點(diǎn)數(shù)目。這就允許了以鍵值為序快速查找第N筆記錄，或是統(tǒng)計(jì)2筆記錄之間的記錄數(shù)目，還有其他很多相關(guān)的操作。

名字取義

Rudolf Bayer 和 Ed McCreight 于1972年，在Boeing Research Labs 工作時(shí)發(fā)明了B 樹(shù)，但是他們沒(méi)有解釋B 代表什么意義（如果有的話）。Douglas Comer 解釋說(shuō): 兩位作者從來(lái)都沒(méi)解釋過(guò)B樹(shù)的原始意義。正如我們所見(jiàn)，“balanced”， “broad” 或 “bushy” 可能適合。其他人建議字母“B”代表 Boeing。源自于他的贊助，不過(guò)，看起來(lái)把B樹(shù)當(dāng)作“Bayer”樹(shù)更合適些

Donald Knuth 在他1980年5月發(fā)表的題為“CS144C classroom lecture about disk storage and B-trees”的論文中推測(cè)了B樹(shù)的名字取義，提出“B”可能意味Boeing 或者Bayer 的名字。

數(shù)據(jù)庫(kù)的問(wèn)題

已排序文件的查找時(shí)間

通常，排序和查找算法會(huì)被通過(guò)大O符號(hào)，刻畫(huà)為比較級(jí)別的數(shù)值。對(duì)一個(gè)有N筆記錄的已排序表進(jìn)行二叉查找，打個(gè)比方說(shuō)，可以在O（log 2 N）比較級(jí)完成。如果表有1,000,000筆記錄,那么定位其中一筆記錄，將在20 個(gè)比較級(jí)內(nèi)完成。 log 2 1,000,000 = 19.931...

大數(shù)據(jù)庫(kù)一直以來(lái)被存儲(chǔ)在磁盤(pán)。從磁盤(pán)上讀取一筆記錄，與之后的比較鍵值操作相比，在花費(fèi)的運(yùn)行時(shí)間上前者處于支配地位。從磁盤(pán)讀取記錄的時(shí)間涉及到一個(gè) 尋道時(shí)間 和 旋轉(zhuǎn)延遲。尋道時(shí)間可能是從0到20或者更多毫秒，旋轉(zhuǎn)延遲平均下來(lái)約是旋轉(zhuǎn)周期的一半。對(duì)于一個(gè)7200 轉(zhuǎn)每分鐘的磁盤(pán)，旋轉(zhuǎn)周期大約是8.33毫秒。像希捷ST3500320NS這樣的磁盤(pán),磁道至磁道的尋道時(shí)間為 0.8毫秒，平均讀取尋道時(shí)間為8.5毫秒。為了簡(jiǎn)化，假設(shè)從磁盤(pán)讀取花費(fèi)10毫秒。

樂(lè)觀來(lái)說(shuō)，如此，在一百萬(wàn)中定位一筆記錄將會(huì)話花費(fèi)20次磁盤(pán)讀取乘上10毫秒每次讀取時(shí)間，總共是0.2秒。

時(shí)間花費(fèi)沒(méi)有那么糟糕的原因是，獨(dú)立的記錄被成組地記錄在磁盤(pán)塊上。一個(gè)磁盤(pán)塊可能為16 千字節(jié)。如果每筆記錄大小為160 字節(jié)，那么一個(gè)塊可以存儲(chǔ)100 筆記錄。上面假設(shè)的磁盤(pán)讀取時(shí)間確切地說(shuō)是讀取一個(gè)完整塊的時(shí)間。一旦磁頭到達(dá)位置，一個(gè)或者更多的磁盤(pán)塊可以以較小的延遲來(lái)完成讀取。對(duì)于100筆記錄每塊，最后差不多6個(gè)比較級(jí)是不需要任何磁盤(pán)讀取的————都在上次讀取操作中完成了。

為進(jìn)一步加速查找，開(kāi)始的13或14個(gè)比較級(jí)（每個(gè)需要一次磁盤(pán)訪問(wèn)）必須要提速。

提升查找的索引

較大程度上的提升是通過(guò)索引來(lái)做到的。在上面的例子中，初始磁盤(pán)讀取從2個(gè)因素限制了查找范圍。這基本上可以通過(guò)創(chuàng)建一個(gè)輔助索引來(lái)改善，這個(gè)索引包含每塊磁盤(pán)塊上的首筆記錄（有時(shí)稱(chēng)為稀疏索引）。這個(gè)輔助索引可能只有原始數(shù)據(jù)庫(kù)的1%大小，但是它可以更快速地被檢索。在輔助索引中查找入口可以告訴我們?cè)谥鲾?shù)據(jù)庫(kù)中要讀去哪一塊;查找輔助索引之后，我們只需要讀取主數(shù)據(jù)庫(kù)中的特定的某一個(gè)磁盤(pán)分塊————通過(guò)一次磁盤(pán)讀取開(kāi)銷(xiāo)。索引可以提供10,000入口，所以，這樣最多需要14個(gè)比較級(jí)。就像主數(shù)據(jù)庫(kù)，輔助索引中最后6個(gè)左右的比較級(jí)可能在相同的磁盤(pán)分塊上。索引可以在大約8次磁盤(pán)讀取中完成查找，目標(biāo)記錄會(huì)在9次磁盤(pán)讀取后獲得。

創(chuàng)建輔助索引的竅門(mén)是可以重復(fù)地給輔助索引創(chuàng)建輔助索引。那樣可以實(shí)現(xiàn)一個(gè)只擁有100 入口，能填滿一整個(gè)磁盤(pán)塊的輔助-輔助索引。

要找到想要的記錄，我們只需要讀取3次磁盤(pán)分塊，而不是14次。讀取和查找輔助-輔助索引中第一個(gè)（而且是唯一的）塊，標(biāo)記了相應(yīng)的輔助索引中的分塊。讀取和查找輔助索引的分塊，標(biāo)記了主數(shù)據(jù)庫(kù)中相應(yīng)的分塊。我們只需要30毫秒，而不是150毫秒就能獲取記錄。

輔助的索引，使得查找問(wèn)題從約為log2N 磁盤(pán)讀取開(kāi)銷(xiāo)的二分查找，變成logbN 磁盤(pán)讀取開(kāi)銷(xiāo)的查找，其中b為分塊因素（每分塊的入口數(shù)目：b = 100 入口每分塊;logb1,000,000 = 3 次讀?。?/span>

在實(shí)際中，如果主數(shù)據(jù)庫(kù)被頻繁查找，輔助-輔助索引和大部分的輔助索引可能會(huì)存儲(chǔ)在磁盤(pán)緩存中，所以它們不會(huì)產(chǎn)生磁盤(pán)讀取。

插入和刪除帶來(lái)的麻煩

如果數(shù)據(jù)庫(kù)不會(huì)改變，那么編制索引就很簡(jiǎn)單，而且索引永遠(yuǎn)不需要改變。如果他們會(huì)改變，那么管理數(shù)據(jù)庫(kù)及其索引就變得非常麻煩。

從數(shù)據(jù)庫(kù)中刪除記錄不會(huì)引起太大問(wèn)題。索引可以保持不變，記錄只需要標(biāo)記為已刪除。數(shù)據(jù)庫(kù)仍然保持有序狀態(tài)。如果會(huì)有很多刪除，之后查找和存儲(chǔ)就不再那么高效了。

在一個(gè)有序文件中進(jìn)行插入將是個(gè)災(zāi)難，因?yàn)樾枰o插入的記錄制造空間。在文件中第一筆記錄后插入記錄需要把所有記錄向后偏移一個(gè)位置。如此的操作在實(shí)際中實(shí)在太過(guò)昂貴。

一種做法是預(yù)留一些空間給插入操作。磁盤(pán)塊有一些空閑空間允許后來(lái)的插入，而不是高密度地填充。這些記錄可以被標(biāo)記為像是已刪除的記錄。

現(xiàn)在，只要塊中存在空間，插入和刪除都可以很快速。如果一個(gè)插入操作在一個(gè)塊上找不到合適的空間，就在臨近的塊中尋找，且要調(diào)整輔助索引。期望是臨近存在足夠的空間，以免重新調(diào)整大量的塊。作為可選方案，可以使用一些非排序的塊。

B樹(shù)運(yùn)用的理念

B樹(shù)使用了以上所有的想法。特別是：

保持鍵值有序，以順序遍歷

使用層次化的索引來(lái)最小化磁盤(pán)讀取

使用不完全填充的塊來(lái)加速插入和刪除

通過(guò)優(yōu)雅的遍歷算法來(lái)保持索引平衡

另外，B樹(shù)通過(guò)保證內(nèi)部節(jié)點(diǎn)至少半滿來(lái)最小化空間浪費(fèi)。一棵B樹(shù)可以處理任意數(shù)目的插入和刪除。

B樹(shù)的弊端

除非完全重建數(shù)據(jù)庫(kù)，否則無(wú)法改變鍵值的最大長(zhǎng)度。這使得許多數(shù)據(jù)庫(kù)系統(tǒng)將人名截?cái)嗟?0字符之內(nèi)。

（其他關(guān)聯(lián)數(shù)組的實(shí)現(xiàn)，例如三元搜索樹(shù)或者開(kāi)散列哈希表，可以動(dòng)態(tài)適應(yīng)任意長(zhǎng)度的鍵值）。

相關(guān)條目

B+樹(shù)

免責(zé)聲明：以上內(nèi)容版權(quán)歸原作者所有，如有侵犯您的原創(chuàng)版權(quán)請(qǐng)告知，我們將盡快刪除相關(guān)內(nèi)容。感謝每一位辛勤著寫(xiě)的作者，感謝每一位的分享。