漫谈数据库索引

一、引言

对数据库索引的关注从未淡出我的们的讨论，那么数据库索引是什么样的？聚集索引与非聚集索引有 什么不同？希望本文对各位同仁有一定的帮助。

二、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）的样例：