一、為什么Oracle使用B-樹而不使用B+樹

因為Oracle葉子節(jié)點存儲的是鍵值+rowid，B-Tree不同于Binary Tree(二叉樹，非常多有兩個子樹)，一棵M階的B-Tree滿足以下條件：

1)每個結(jié)點至多有M個孩子；

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

3)根結(jié)點至少有兩個孩子(除非該樹僅包含一個結(jié)點)；

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

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

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

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

延伸閱讀：

二、什么是索引

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

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

B)對于非聚集索引，有些查詢甚至可以不訪問數(shù)據(jù)頁。

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

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

當(dāng)然，眾所周知，雖然索引可以提高查詢速度，但是它們也會導(dǎo)致數(shù)據(jù)庫系統(tǒng)更新數(shù)據(jù)的性能下降，因為大部分?jǐn)?shù)據(jù)更新需要同時更新索引。