多向樹

多向樹（Multiway tree）又稱多向檢索樹，是高度—平衡二叉檢索樹，它的檢索、插入和刪除算法所需的執行時間與log₂(N)成正比，其中N是樹中結點數目。當多向檢索樹能保存在主存貯器時，它是很有用的。然而，當利用大型資料庫時，這一點往往不可能做到。與此相反，樹的結點是保存在外部存貯器。

基本介紹

• 中文名：多向樹
• 外文名：Multiway tree
• 定 義：高度-平衡二叉檢索樹
• 套用學科：計算機原理，數據結構術語

概念

多向樹（Multiway tree）又稱多向檢索樹，是高度—平衡二叉檢索樹，它的檢索、插入和刪除算法所需的執行時間與log₂(N)成正比，其中N是樹中結點數目。當多向檢索樹能保存在主存貯器時，它是很有用的。然而，當利用大型資料庫時，這一點往往不可能做到。與此相反，樹的結點是保存在外部存貯器。諸如磁碟或磁鼓。每個結點的項都存貯在磁碟或磁鼓的實際地址字的相鄰模組中，而結點之間的連線就是盤與鼓的地址。當結點被處理時，首先必須將結點的所有欄位複製到計算機的主存貯器中。訪問在主存貯器內的樹和訪問不在主存貯器的樹之間的重要差異，就是把結點欄位複製到主存貯器需要時間，一般而言，從主存貯器存取一個字所需的存取時間等於或小於1微秒，而從磁碟或磁鼓隨機存取一個字卻需要毫秒量級的時間。然而，指要一旦已經從磁碟或磁鼓存取一個給定的字，則與之相鄰的字就可以用主存貯器的速度來存取了。存取的第一個字需要較時間，是由於讀出磁頭對準所需字定位和磁碟或磁鼓轉動到適當位置的時間而形成的。因為對一些相鄰字的存取能與單個字存取差不多同樣快速，把很多信息儘可能存貯在每個結點之中是有利的。實際上，採用多向樹比採用每個結點有個關鍵項和兩個鏈的二叉樹會有利一些。但是，多向樹通常會遇到與二叉樹相同的檢索分類低效率。為了克服低效率，引入平衡多向樹的概念。

工作原理

當一顆樹由於插入或刪除操作而失去平衡時，需要恢復樹的平衡。結論當然是，要找到執行時間與log₂(N)成正比的插入和刪除算法，且保持一種高效率的檢索結構。

多向檢索樹的每個結點包含兩部分：執行結點字數的指示字數據（標誌）和數值數據。由於多向樹主要套用與資料庫，因此其標誌通常被稱為鍵。在後面敘述中將遵從這個約定，若多向檢索樹的一個節點具有N+1個子對，則它同樣具有N個鍵和N個數值。記鍵的值為，記N+1個後代結點的地址為。而且鍵順序排列，使。此外，子樹也有順序排列，使0子樹的所有鍵值都小於；當小於N時，子樹的所有鍵值落在與值之間，且N子樹的所有鍵值都大於。這個有序性應該對樹的每個結點都成立，使得樹能有效地檢索。

應該明確指出，每個不同結點具有數量不同的子樹，因而每個結點應該包含一個指明子樹數目的m值。