简单说说B+树索引的结构和原理

B+树结构是1972年被发明的，一经出现就成为数据库索引的首选。

上面这张图来自于首发B+树的那篇论文。分支节点只做索引，只有叶节点存储数据。索引键左侧的块都小于索引键值，右侧的都大于索引键值。

今天老白以Oracle的B树索引为例，来分析一下索引的结构。实际上在老白的《DBA的思想天空》中就讨论过索引的结构，B树索引是一棵带双向叶节点链的B+树，如下图：

图1

我们可以用一个实际的例子来看一棵索引树的结构（老白创建了一个索引，然后用treedump事件把索引的结构DUMP出来）

图2

这个TREEDUMP中，我们可以看出一共有16个索引块，其中一个枝节点，带有15个指针，指向15个页块。整个索引一共只有2层。我们来看看枝节点的结构。

通过Oracle的工具我们计算出枝节点的文件号和块号，然后DUMP出来：

这里我们看到只有14条记录，和上面的15条似乎有点对不上，大家可以看到每个level都是从-1开始编码的，小于最小那个键值的就是-1号块，不需要一个指针了，这样可以节约一个指针。从这里可以看出Oracle在设计上处处都透着节约。

我们下面来看一个叶节点块。

大家注意3的位置就是键值，COL0，4的位置COL1就是该键值对应的数据表的ROWID，通过这个ROW就可以找到这条记录了。大家注意下1和2，这就是叶节点双向链表。大家可以看到，kdxlenxt是下一个叶节点，而Kdxleprv是前一个叶节点。具体大家可以对照图2的数据。叶节点链使扫描变得更为高效。只要找到第一条符合条件的记录，如果使>=操作，就顺着叶节点链往高查找，直到不满足条件为止。如果使<操作，那么就从该值开始找到第一个小于该条件的记录，然后向下扫描，直到所有符合条件的记录被找到就行了。

下面我们举个例子

这是一个一级枝节点，一级叶节点的索引。id>=100的数据指向208，200的指向209，以此类推。这里有一个207块，就是-1号节点，存储小于100的数据。我们来看看索引是如何工作的。select … from … where id=100

索引范围扫描（如果是主键就是索引唯一性扫描）

select … from … where id<100

索引范围扫描

select … from … where id>
100 and id<300

索引范围扫描

select id from …  order by id

全索引扫描

select id from … order by id desc

全索引扫描

select id from …

快速索引扫描

最后我们谈谈Postgresql的索引，实际上虽然实现方式有些差异，Postgresql的索引结构和ORACLE十分类似。下面的论述来自于老白查阅的Pat Shaughnessy 在20,000 Leagues Under ActiveRecord大会上的演讲稿。包括截图都是，并不是老白自己研究的结果。分享出来只是为了让大家更好的理解PG的索引结构。

PG的索引多了一个bitmap字段，这个字段是用来指示键值中是否包含NULL。

t_tid是指向一个元组的指针。而t_info包含一些统计值，包括有多少个值以及是否包含NULL等。下面的例子更为直观：

今天的内容就到这里。PG的源码注释写的相当完善，对PG索引有兴趣深入研究的朋友可以去阅读。