幾種常用樹介紹
Binary Search Tree(二叉查找樹、二叉排序樹、二叉搜索樹)
指一棵空樹或者具有下列性質的 二叉樹 :
- 1)若任意節點的左子樹不空,則左子樹上所有結點的值均小于它的根結點的值;
- 2)任意節點的右子樹不空,則右子樹上所有結點的值均大于它的根結點的值;
- 3)任意節點的左、右子樹也分別為二叉查找樹。
- 4)沒有鍵值相等的節點(no duplicate nodes)。
Balanced Binary Search Tree(平衡二叉查找樹、AVL樹)
- 在AVL樹中任何節點的兩個 子樹 的高度最大差別為一,所以它也被稱為 高度平衡樹 。查找、插入和刪除在平均和最壞情況下都是 O (log? n )。增加和刪除可能需要通過一次或多次 樹旋轉 來重新平衡這個樹。
- 平衡二叉樹是一個重要的數據結構,它有很均衡的插入、刪除以及查詢性能(時間復雜度都是O(logn))。Linux2.4以前的內核中,虛擬內存管理中用的容器就是AVL Tree。AVL Tree對平衡的要求是比較嚴格的,它要求左右子數之間的長度差不能大于1。
紅黑樹
-
紅黑樹是每個節點都帶有 顏色 屬性的 二叉查找樹 ,顏色為 紅色 或 黑色 。在二叉查找樹強制一般要求以外,對于任何有效的紅黑樹我們增加了如下的額外要求:
性質1. 節點是紅色或黑色。
性質2. 根是黑色。
性質3. 所有葉子都是黑色(葉子是NIL節點)。
性質4. 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)
性質5. 從任一節點到其每個葉子的所有 簡單路徑 都包含相同數目的黑色節點。
二叉查找樹但若是一棵具有n個結點的線性鏈,則此些操作最壞情況運行時間為O(n),但是 紅黑樹,能保證在最壞情況下,基本的動態幾何操作的時間均為O(lgn)。
從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。
詳細介紹可以參考: http://blog.csdn.net/v_JULY_v/article/details/6105630 等的詳細介紹。
平衡二叉樹和紅黑樹比較:
AVL是嚴格平衡樹,因此在增加或者刪除節點的時候,根據不同情況,旋轉的次數比紅黑樹要多;
紅黑是用非嚴格的平衡來換取增刪節點時候旋轉次數的降低;
所以簡單說,如果你的應用中,搜索的次數遠遠大于插入和刪除,那么選擇AVL,如果搜索,插入刪除次數幾乎差不多,或者插入更多,應該選擇RB
B樹
???? 是一個節點可以擁有多于2個子節點的 二叉查找樹 。
-
就是大規模數據存儲中,實現索引查詢這樣一個實際背景下,樹節點存儲的元素數量是有限的(如果元素數量非常多的話,查找就退化成節點內部的線性查找了),這樣導致二叉查找樹結構由于 樹的深度過大而造成磁盤I/O讀寫過于頻繁,進而導致查詢效率低下 (為什么會出現這種情況,待會在外部存儲器-磁盤中有所解釋),那么如何減少樹的深度(當然是不能減少查詢的數據量),一個基本的想法就是:采用 多叉樹 結構(由于樹節點元素數量是有限的,自然該節點的子樹數量也就是有限的)。
在大規模數據存儲方面,大量數據存儲在外存磁盤中,而在外存磁盤中讀取/寫入塊(block)中某數據時,首先需要定位到磁盤中的某塊,如何有效地查找磁盤中的數據,需要一種合理高效的外存數據結構,就是B-tree結構。
B樹與紅黑樹最大的不同在于,B樹的結點可以有許多子女,從幾個到幾千個。那為什么又說B樹與紅黑樹很相似呢?因為與紅黑樹一樣,一棵含n個結點的B樹的高度也為O(lgn),但可能比一棵紅黑樹的高度小許多,應為它的分支因子比較大。所以,B樹可以在O(logn)時間內,實現各種如插入(insert),刪除(delete)等動態集合操作。
B+樹
????? B + -tree :是應文件系統所需而產生的一種 B-tree的變形樹。
???? 一棵m階的B+樹和m階的B樹的異同點在于:
-
?有n棵子樹的結點中含有n-1 個關鍵字; (與B 樹n棵子樹有n-1個關鍵字 保持一致,參照: http://en.wikipedia.org/wiki/B%2B_tree#Overview ,而下面 B+樹的圖可能有問題 ,請讀者注意)
????? 2.所有的葉子結點中包含了全部關鍵字的信息,及指向含有這些關鍵字記錄的指針,且葉子結點本身依關鍵字的大小自小而大的順序鏈接。 (而B 樹的葉子節點并沒有包括全部需要查找的信息)
????? 3. 所有的非終端結點可以看成是索引部分 ,結點中僅含有其子樹根結點中最大(或最小)關鍵字。 (而B 樹的非終節點也包含需要查找的有效信息)
a) 為什么說 B + -tree 比B 樹更適合實際應用中操作系統的文件索引和數據庫索引?
1) B + -tree的磁盤讀寫代價更低
B + -tree 的內部結點并沒有指向關鍵字具體信息的指針。因此其內部結點相對B 樹更小。如果把所有同一內部結點的關鍵字存放在同一盤塊中,那么盤塊所能容納的關鍵字數量也越多。一次性讀入內存中的需要查找的關鍵字也就越多。相對來說IO讀寫次數也就降低了。
舉個例子,假設磁盤中的一個盤塊容納16bytes,而一個關鍵字2bytes,一個關鍵字具體信息指針2bytes。一棵9階 B-tree(一個結點最多8個關鍵字)的內部結點需要2個盤快。而 B +? 樹內部結點只需要1個盤快。當需要把內部結點讀入內存中的時候,B 樹就比 B +? 樹多一次盤塊查找時間(在磁盤中就是盤片旋轉的時間)。
2) B + -tree的查詢效率更加穩定
由于非終結點并不是最終指向文件內容的結點,而只是葉子結點中關鍵字的索引。所以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同,導致每一個數據的查詢效率相當。
數據庫索引采用B+樹的主要原因是 B樹在提高了磁盤IO性能的同時并沒有解決元素遍歷的效率低下的問題。正是為了解決這個問題,B+樹應運而生。B+樹只要遍歷葉子節點就可以實現整棵樹的遍歷。而且在數據庫中基于范圍的查詢是非常頻繁的,而B樹不支持這樣的操作(或者說效率太低)。
B * -tree
-
B*-tree是 B + -tree 的變體,在 B + 樹的基礎上(所有的葉子結點中包含了全部關鍵字的信息,及指向含有這些關鍵字記錄的指針),B*樹中非根和非葉子結點再增加指向兄弟的指針;B*樹定義了非葉子結點關鍵字個數至少為(2/3)*M,即塊的最低使用率為2/3(代替B+樹的1/2)。給出了一個簡單實例,如下圖所示:
B+樹的分裂:當一個結點滿時,分配一個新的結點,并將原結點中1/2的數據復制到新結點,最后在父結點中增加新結點的指針;B+樹的分裂只影響原結點和父結點,而不會影響兄弟結點,所以它不需要指向兄弟的指針。
B*樹的分裂:當一個結點滿時,如果它的下一個兄弟結點未滿,那么將一部分數據移到兄弟結點中,再在原結點插入關鍵字,最后修改父結點中兄弟結點的關鍵字(因為兄弟結點的關鍵字范圍改變了);如果兄弟也滿了,則在原結點與兄弟結點之間增加新結點,并各復制1/3的數據到新結點,最后在父結點增加新結點的指針。
所以,B*樹分配新結點的概率比B+樹要低,空間使用率更高;
現在一般主流的數據庫索引一般都是用的B/B+樹系列,包括MySQL及NoSQL中的MongoDB。
LSM-tree(Log Structured merge -tree)
?????????? 詳細參考: http://duanple.blog.163.com/blog/static/7097176720120391321283/
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
