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

因?yàn)镺racle葉子節(jié)點(diǎn)存儲的是鍵值+rowid，B-Tree不同于Binary Tree(二叉樹，非常多有兩個(gè)子樹)，一棵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è)孩子(除非該樹僅包含一個(gè)結(jié)點(diǎn))；

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

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

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

對于每個(gè)結(jié)點(diǎn)，主要包含一個(gè)關(guān)鍵字?jǐn)?shù)組Key[]，一個(gè)指針數(shù)組(指向兒子)Son[]。在B-Tree內(nèi)，查找的流程是：使用順序查找(數(shù)組長度較短 時(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í)，查找過程失敗。

延伸閱讀：

二、什么是索引

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

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

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

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

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

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