一、為什么Oracle使用B-樹(shù)而不使用B+樹(shù)

因?yàn)镺racle葉子節(jié)點(diǎn)存儲(chǔ)的是鍵值+rowid，B-Tree不同于Binary Tree(二叉樹(shù)，非常多有兩個(gè)子樹(shù))，一棵M階的B-Tree滿足以下條件：

1)每個(gè)結(jié)點(diǎn)至多有M個(gè)孩子；

2)除根結(jié)點(diǎn)和葉結(jié)點(diǎn)外，其它每個(gè)結(jié)點(diǎn)至少有M/2個(gè)孩子；

3)根結(jié)點(diǎn)至少有兩個(gè)孩子(除非該樹(shù)僅包含一個(gè)結(jié)點(diǎn))；

4)所有葉結(jié)點(diǎn)在同一層，葉結(jié)點(diǎn)不包含任何關(guān)鍵字信息；

5)有K個(gè)關(guān)鍵字的非葉結(jié)點(diǎn)恰好包含K+1個(gè)孩子；

另外，對(duì)于一個(gè)結(jié)點(diǎn)，其內(nèi)部的關(guān)鍵字是從小到大排序的。以下是B-Tree(M=4)的樣例：

對(duì)于每個(gè)結(jié)點(diǎn)，主要包含一個(gè)關(guān)鍵字?jǐn)?shù)組Key[]，一個(gè)指針數(shù)組(指向兒子)Son[]。在B-Tree內(nèi)，查找的流程是：使用順序查找(數(shù)組長(zhǎng)度較短 時(shí))或折半查找方法查找Key[]數(shù)組，若找到關(guān)鍵字K，則返回該結(jié)點(diǎn)的地址及K在Key[]中的位置；否則，可確定K在某個(gè)Key[i]和 Key[i+1]之間，則從Son[i]所指的子結(jié)點(diǎn)繼續(xù)查找，直到在某結(jié)點(diǎn)中查找成功；或直至找到葉結(jié)點(diǎn)且葉結(jié)點(diǎn)中的查找仍不成功時(shí)，查找過(guò)程失敗。

延伸閱讀：

二、什么是索引

在數(shù)據(jù)庫(kù)中，索引的含義與日常意義上的“索引”一詞并無(wú)多大區(qū)別(想想小時(shí)候查字典)，它是用于提高數(shù)據(jù)庫(kù)表數(shù)據(jù)訪問(wèn)速度的數(shù)據(jù)庫(kù)對(duì)象。

A)索引可以避免全表掃描。多數(shù)查詢(xún)可以?xún)H掃描少量索引頁(yè)及數(shù)據(jù)頁(yè)，而不是遍歷所有數(shù)據(jù)頁(yè)。

B)對(duì)于非聚集索引，有些查詢(xún)甚至可以不訪問(wèn)數(shù)據(jù)頁(yè)。

C)聚集索引可以避免數(shù)據(jù)插入操作集中于表的最后一個(gè)數(shù)據(jù)頁(yè)。

D)一些情況下，索引還可用于避免排序操作。

當(dāng)然，眾所周知，雖然索引可以提高查詢(xún)速度，但是它們也會(huì)導(dǎo)致數(shù)據(jù)庫(kù)系統(tǒng)更新數(shù)據(jù)的性能下降，因?yàn)榇蟛糠謹(jǐn)?shù)據(jù)更新需要同時(shí)更新索引。