(3)B+樹(shù)

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

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

　　2.非葉子結(jié)點(diǎn)的子樹(shù)指針與關(guān)鍵字個(gè)數(shù)相同;

　　3.非葉子結(jié)點(diǎn)的子樹(shù)指針P[i]，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹(shù)(B-樹(shù)是開(kāi)區(qū)間);

　　5.為所有葉子結(jié)點(diǎn)增加一個(gè)鏈指針;

　　6.所有關(guān)鍵字都在葉子結(jié)點(diǎn)出現(xiàn);

　　如：(M=3)

　　B+的搜索與B-樹(shù)也基本相同，區(qū)別是B+樹(shù)只有達(dá)到葉子結(jié)點(diǎn)才命中(B-樹(shù)可以在非葉子結(jié)點(diǎn)命中)，其性能也等價(jià)于在關(guān)鍵字全集做一次二分查找;

　　B+的特性：

　　1.所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點(diǎn)的鏈表中(稠密索引)，且鏈表中的關(guān)鍵字恰好是有序的;

　　2.不可能在非葉子結(jié)點(diǎn)命中;

　　3.非葉子結(jié)點(diǎn)相當(dāng)于是葉子結(jié)點(diǎn)的索引(稀疏索引)，葉子結(jié)點(diǎn)相當(dāng)于是存儲(chǔ)(關(guān)鍵字)數(shù)據(jù)的數(shù)據(jù)層;

　　4.更適合文件索引系統(tǒng);

　　(4)B*樹(shù)

　　是B+樹(shù)的變體，在B+樹(shù)的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針;

　　B*樹(shù)定義了非葉子結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)至少為(2/3)*M，即塊的最低使用率為2/3(代替B+樹(shù)的1/2);

　　B+樹(shù)的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)，分配一個(gè)新的結(jié)點(diǎn)，并將原結(jié)點(diǎn)中1/2的數(shù)據(jù)復(fù)制到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)中增加新結(jié)點(diǎn)的指針;B+樹(shù)的分裂只影響原結(jié)點(diǎn)和父結(jié)點(diǎn)，而不會(huì)影響兄弟結(jié)點(diǎn)，所以它不需要指向兄弟的指針;

　　B*樹(shù)的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)，如果它的下一個(gè)兄弟結(jié)點(diǎn)未滿，那么將一部分?jǐn)?shù)據(jù)移到兄弟結(jié)點(diǎn)中，再在原結(jié)點(diǎn)插入關(guān)鍵字，最后修改父結(jié)點(diǎn)中兄弟結(jié)點(diǎn)的關(guān)鍵字(因?yàn)樾值芙Y(jié)點(diǎn)的關(guān)鍵字范圍改變了);如果兄弟也滿了，則在原結(jié)點(diǎn)與兄弟結(jié)點(diǎn)之間增加新結(jié)點(diǎn)，并各復(fù)制1/3的數(shù)據(jù)到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)增加新結(jié)點(diǎn)的指針;

　　所以，B*樹(shù)分配新結(jié)點(diǎn)的概率比B+樹(shù)要低，空間使用率更高;

　　(5)紅黑樹(shù)

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

　　map就是采用紅黑樹(shù)存儲(chǔ)的，紅黑樹(shù)(RB Tree)是平衡二叉樹(shù)，其優(yōu)點(diǎn)就是樹(shù)到葉子節(jié)點(diǎn)深度一致，查找的效率也就一樣，為logN。在實(shí)行查找，插入，刪除的效率都一致，而當(dāng)是全部靜態(tài)數(shù)據(jù)時(shí)，沒(méi)有太多優(yōu)勢(shì)，可能采用hash表各合適。

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

　　現(xiàn)在知道如何選擇了嗎?權(quán)衡三個(gè)因素: 查找速度, 數(shù)據(jù)量, 內(nèi)存使用。

　　紅黑樹(shù)的每個(gè)節(jié)點(diǎn)上的屬性除了有一個(gè)key、3個(gè)指針：parent、lchild、rchild以外，還多了一個(gè)屬性：color。它只能是兩種顏色：紅或黑。而紅黑樹(shù)除了具有二叉搜索樹(shù)的所有性質(zhì)之外，還具有以下4點(diǎn)性質(zhì)：

　　1. 根節(jié)點(diǎn)是黑色的。

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

　　3. 紅色節(jié)點(diǎn)的父、左子、右子節(jié)點(diǎn)都是黑色。

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

　　軟考程序員考試歷年真題重點(diǎn)題總結(jié)及答案

　　2011年上半年軟考報(bào)名時(shí)間及方式匯總

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