一、為什么Oracle使用B-樹而不使用B+樹
因?yàn)镺racle葉子節(jié)點(diǎn)存儲(chǔ)的是鍵值+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è)孩子;
另外,對(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ù)組長度較短 時(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ù)庫對(duì)象。
A)索引可以避免全表掃描。多數(shù)查詢可以僅掃描少量索引頁及數(shù)據(jù)頁,而不是遍歷所有數(shù)據(jù)頁。
B)對(duì)于非聚集索引,有些查詢甚至可以不訪問數(shù)據(jù)頁。
C)聚集索引可以避免數(shù)據(jù)插入操作集中于表的最后一個(gè)數(shù)據(jù)頁。
D)一些情況下,索引還可用于避免排序操作。
當(dāng)然,眾所周知,雖然索引可以提高查詢速度,但是它們也會(huì)導(dǎo)致數(shù)據(jù)庫系統(tǒng)更新數(shù)據(jù)的性能下降,因?yàn)榇蟛糠謹(jǐn)?shù)據(jù)更新需要同時(shí)更新索引。