oracle是b树 MySQL是B 树_数据库索引--B树/B+树

一、 引言

对数据库索引的关注从未淡出我的们的讨论，那么数据库索引是什么样的？分哪些类型？索引的存储是怎样的？聚集索引与非聚集索引有什么不同？

二、B-Tree

我们常见的数据库系统，其索引使用的数据结构多是B-Tree或者B+Tree。例如，MsSql使用的是B+Tree，Oracle及Sysbase使用的是B-Tree。所以在最开始，简单地介绍一下B-Tree。

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[]数组，若找到关键字