一、为什么Oracle使用B-树而不使用B+树

因为Oracle叶子节点存储的是键值+rowid，B-Tree不同于Binary Tree(二叉树，非常多有两个子树)，一棵M阶的B-Tree满足以下条件：

1)每个结点至多有M个孩子；

2)除根结点和叶结点外，其它每个结点至少有M/2个孩子；

3)根结点至少有两个孩子(除非该树仅包含一个结点)；

4)所有叶结点在同一层，叶结点不包含任何关键字信息；

5)有K个关键字的非叶结点恰好包含K+1个孩子；

另外，对于一个结点，其内部的关键字是从小到大排序的。以下是B-Tree(M=4)的样例：

对于每个结点，主要包含一个关键字数组Key[]，一个指针数组(指向儿子)Son[]。在B-Tree内，查找的流程是：使用顺序查找(数组长度较短 时)或折半查找方法查找Key[]数组，若找到关键字K，则返回该结点的地址及K在Key[]中的位置；否则，可确定K在某个Key[i]和 Key[i+1]之间，则从Son[i]所指的子结点继续查找，直到在某结点中查找成功；或直至找到叶结点且叶结点中的查找仍不成功时，查找过程失败。

延伸阅读：

二、什么是索引

在数据库中，索引的含义与日常意义上的“索引”一词并无多大区别(想想小时候查字典)，它是用于提高数据库表数据访问速度的数据库对象。

A)索引可以避免全表扫描。多数查询可以仅扫描少量索引页及数据页，而不是遍历所有数据页。

B)对于非聚集索引，有些查询甚至可以不访问数据页。

C)聚集索引可以避免数据插入操作集中于表的最后一个数据页。

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

当然，众所周知，虽然索引可以提高查询速度，但是它们也会导致数据库系统更新数据的性能下降，因为大部分数据更新需要同时更新索引。

上一篇

redis和平常写的数据结构有什么区别?

下一篇

负权形成环路的图为什么不能用弗洛伊德算法求任意两点之间的最短路径?