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

昨天PG社区在讨论B树索引的结构(这里B树是一个泛泛的称呼，搞数学的人要严谨，应该说是B+树。老白翻了翻以前写过的一些资料，整理一下，和大家分享。一般数据库的索引都使用B+树结构，这是一种变种的B树结构。和B树相同的是一个节点内可以有多个指针(不同于二叉树)，不同的是B+树的枝节点里面没有数据，只有叶节点中有数据。在BLOCK SIZE相同的情况下，这种结构有助于用更少的枝块来构建一棵平衡的树，让树的层次尽可能的小。B+树结构是1972年被发明的，一经出现就成为数据库索引的首选。

上面这张图来自于首发B+树的那篇论文。分支节点只做索引，只有叶节点存储数据。索引键左侧的块都小于索引键值，右侧的都大于索引键值。今天老白以的B树索引为例，来分析一下索引的结构。实际上在老白的《DBA的思想天空》中就讨论过索引的结构，B树索引是一棵带双向叶节点链的B+树，如下图：

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