一、B樹(shù)的應(yīng)用

1、B樹(shù)大量應(yīng)用在數(shù)據(jù)庫(kù)和文件系統(tǒng)當(dāng)中。

它的設(shè)計(jì)思想是，將相關(guān)數(shù)據(jù)盡量集中在一起，以便一次讀取多個(gè)數(shù)據(jù)，減少硬盤(pán)操作次數(shù)。B樹(shù)算法減少定位記錄時(shí)所經(jīng)歷的中間過(guò)程，從而加快存取速度。

假定一個(gè)節(jié)點(diǎn)可以容納100個(gè)值，那么3層的B樹(shù)可以容納100萬(wàn)個(gè)數(shù)據(jù)，如果換成二叉查找樹(shù)，則需要20層！假定操作系統(tǒng)一次讀取一個(gè)節(jié)點(diǎn)，并且根節(jié)點(diǎn)保留在內(nèi)存中，那么B樹(shù)在100萬(wàn)個(gè)數(shù)據(jù)中查找目標(biāo)值，只需要讀取兩次硬盤(pán)。

如mongoDB數(shù)據(jù)庫(kù)使用，單次查詢(xún)平均快于Mysql（但側(cè)面來(lái)看Mysql至少平均查詢(xún)耗時(shí)差不多）

二、B+樹(shù)的應(yīng)用

mysql使用B+樹(shù)作為索引：

B+樹(shù)相對(duì)B樹(shù)的優(yōu)點(diǎn)：

①B+樹(shù)的所有Data域在葉子節(jié)點(diǎn)，一般來(lái)說(shuō)都會(huì)進(jìn)行一個(gè)優(yōu)化，就是將所有的葉子節(jié)點(diǎn)用指針串聯(lián)起來(lái)，遍歷葉子節(jié)點(diǎn)就能獲取全部數(shù)據(jù)，這樣就能進(jìn)行區(qū)間訪問(wèn)了。

②IO一次讀數(shù)據(jù)是從磁盤(pán)上讀的，磁盤(pán)容量是固定的，取數(shù)據(jù)量大小是固定的，非葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，節(jié)點(diǎn)小，磁盤(pán)IO次數(shù)就少。

1、MYISAM

MyISAM中有兩種索引，分別是主索引和輔助索引，在這里面的主索引使用具有唯一性的鍵值進(jìn)行創(chuàng)建，而輔助索引中鍵值可以是相同的。MyISAM分別會(huì)存一個(gè)索引文件和數(shù)據(jù)文件。它的主索引是非聚集索引。當(dāng)我們查詢(xún)的時(shí)候我們找到葉子節(jié)點(diǎn)中保存的地址，然后通過(guò)地址我們找到所對(duì)應(yīng)的信息。

2、INNODB

InnoDB索引和MyISAM最大的區(qū)別是它只有一個(gè)數(shù)據(jù)文件，在InnoDB中，表數(shù)據(jù)文件本身就是按B+Tree組織的一個(gè)索引結(jié)構(gòu)，這棵樹(shù)的葉節(jié)點(diǎn)數(shù)據(jù)域保存了完整的數(shù)據(jù)記錄。所以我們又把它的主索引叫做聚集索引。而它的輔助索引和MyISAM也會(huì)有所不同，它的輔助索引都是將主鍵作為數(shù)據(jù)域。所以，這樣當(dāng)我們查找的時(shí)候通過(guò)輔助索引要先找到主鍵，然后通過(guò)主索引再找到對(duì)于的主鍵，得到信息。

MyISAM表索引在處理文本索引時(shí)更具優(yōu)勢(shì)，而INNODB表索引在其它類(lèi)型上更具效率優(yōu)勢(shì)，同時(shí)MySQL高并發(fā)需要事務(wù)場(chǎng)景時(shí)，只能使用INNODB表

三、紅黑樹(shù)

紅黑樹(shù)往往出現(xiàn)由于樹(shù)的深度過(guò)大而造成磁盤(pán)IO讀寫(xiě)過(guò)于頻繁，進(jìn)而導(dǎo)致效率低下的情況在數(shù)據(jù)較小，可以完全放到內(nèi)存中時(shí)，紅黑樹(shù)的時(shí)間復(fù)雜度比B樹(shù)低。

如linux中進(jìn)程的調(diào)度用的是紅黑樹(shù)。

反之，數(shù)據(jù)量較大，外存中占主要部分時(shí)，B樹(shù)因其讀磁盤(pán)次數(shù)少，而具有更快的速度。