一、引言

对数据库索引的关注从未淡出我的们的讨论，那么数据库索引是什么样的？聚集索引与非聚集索引有什么不同？希望本文对各位同仁有一定的帮助。有不少存疑的地方，诚心希望各位不吝赐教指正，共同进步。[最近首页之争沸沸扬扬，也不知道这个放在这合适么，苦劳？功劳？……]

?

?

二、 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[] 数组，若找到关键字 K ，则返回该结点的地址及 K 在 Key[] 中的位置；否则，可确定 K 在某个 Key[i] 和 Key[i+1] 之间，则从 Son[i] 所指的子结点继续查找，直到在某结点中查找成功；或直至找到叶结点且叶结点中的查找仍不成功时，查找过程失败。

接着，我们使用以下图片演示如何生成 B-Tree （ M=4 ，依次插入 1~6 ）：
从图可见，当我们插入关键字 4 时，由于原结点已经满了，故进行分裂，基本按一半的原则进行分裂，然后取出中间的关键字 2 ，升级（这里是成为根结点）。其它的依类推，就是这样一个大概的过程。