(3)B+樹

　　B+樹是B-樹的變體，也是一種多路搜索樹：

　　1.其定義基本與B-樹同，除了：

　　2.非葉子結點的子樹指針與關鍵字個數相同;

　　3.非葉子結點的子樹指針P[i]，指向關鍵字值屬于[K[i], K[i+1])的子樹(B-樹是開區間);

　　5.為所有葉子結點增加一個鏈指針;

　　6.所有關鍵字都在葉子結點出現;

　　如：(M=3)

　　B+的搜索與B-樹也基本相同，區別是B+樹只有達到葉子結點才命中(B-樹可以在非葉子結點命中)，其性能也等價于在關鍵字全集做一次二分查找;

　　B+的特性：

　　1.所有關鍵字都出現在葉子結點的鏈表中(稠密索引)，且鏈表中的關鍵字恰好是有序的;

　　2.不可能在非葉子結點命中;

　　3.非葉子結點相當于是葉子結點的索引(稀疏索引)，葉子結點相當于是存儲(關鍵字)數據的數據層;

　　4.更適合文件索引系統;

　　(4)B*樹

　　是B+樹的變體，在B+樹的非根和非葉子結點再增加指向兄弟的指針;

　　B*樹定義了非葉子結點關鍵字個數至少為(2/3)*M，即塊的最低使用率為2/3(代替B+樹的1/2);

　　B+樹的分裂：當一個結點滿時，分配一個新的結點，并將原結點中1/2的數據復制到新結點，最后在父結點中增加新結點的指針;B+樹的分裂只影響原結點和父結點，而不會影響兄弟結點，所以它不需要指向兄弟的指針;

　　B*樹的分裂：當一個結點滿時，如果它的下一個兄弟結點未滿，那么將一部分數據移到兄弟結點中，再在原結點插入關鍵字，最后修改父結點中兄弟結點的關鍵字(因為兄弟結點的關鍵字范圍改變了);如果兄弟也滿了，則在原結點與兄弟結點之間增加新結點，并各復制1/3的數據到新結點，最后在父結點增加新結點的指針;

　　所以，B*樹分配新結點的概率比B+樹要低，空間使用率更高;

　　(5)紅黑樹

　　紅黑樹(Red-Black Tree)是二叉搜索樹(BinarySearch Tree)的一種改進。我們知道二叉搜索樹在最壞的情況下可能會變成一個鏈表(當所有節點按從小到大的順序依次插入后)。而紅黑樹在每一次插入或刪除節點之后都會花O(log N)的時間來對樹的結構作修改，以保持樹的平衡。也就是說，紅黑樹的查找方法與二叉搜索樹完全一樣;插入和刪除節點的的方法前半部分節與二叉搜索樹完全一樣，而后半部分添加了一些修改樹的結構的操作。

　　map就是采用紅黑樹存儲的，紅黑樹(RB Tree)是平衡二叉樹，其優點就是樹到葉子節點深度一致，查找的效率也就一樣，為logN。在實行查找，插入，刪除的效率都一致，而當是全部靜態數據時，沒有太多優勢，可能采用hash表各合適。

　　相對來說，hash_map是一個hashtable占用內存更多，查找效率高一些，但是hash的時間比較費時�？傮w而言，hash_map 查找速度會比map快，而且查找速度基本和數據數據量大小無關，屬于常數級別;而map的查找速度是log(n)級別。并不一定常數就比log(n)小， hash還有hash函數的耗時，明白了吧，如果你考慮效率，特別是在元素達到一定數量級時，考慮考慮hash_map。但若你對內存使用特別嚴格，希望程序盡可能少消耗內存，那么一定要小心，hash_map可能會讓你陷入尷尬，特別是當你的hash_map對象特別多時，你就更無法控制了，而且 hash_map的構造速度較慢。

　　現在知道如何選擇了嗎?權衡三個因素: 查找速度, 數據量, 內存使用。

　　紅黑樹的每個節點上的屬性除了有一個key、3個指針：parent、lchild、rchild以外，還多了一個屬性：color。它只能是兩種顏色：紅或黑。而紅黑樹除了具有二叉搜索樹的所有性質之外，還具有以下4點性質：

　　1. 根節點是黑色的。

　　2. 空節點是黑色的(紅黑樹中，根節點的parent以及所有葉節點lchild、rchild都不指向NULL，而是指向一個定義好的空節點)。

　　3. 紅色節點的父、左子、右子節點都是黑色。

　　4. 在任何一棵子樹中，每一條從根節點向下走到空節點的路徑上包含的黑色節點數量都相同。

　　軟考程序員考試歷年真題重點題總結及答案

　　2011年上半年軟考報名時間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)