更新(甲骨文索引内部存档版本):http://web.archive.org/web/20161221112438/http://www.toadworld.com/platforms/oracle/w/wiki/11001.oracle-b-tree-index-from-the-concept-to-internals
旧的(原始链接不再存在):
注:
数据库不直接实现基于B-树的索引，而是基于一种称为B+树的变体.根据维基百科的说法:
可以将B+树视为B-树，其中每个 node 只包含关键字(不包含关键字-值对)，并且在底部添加了带有链接叶的附加级别.
一般来说，数据库使用面向挡路的存储，并且b+树比b-tree更适合于此.
这些块的大小是固定的，并且留有一些空闲空间来适应将来值或密钥大小的更改.
挡路可以是叶(保存实际数据)或分支(保存指向叶 node 的指针)
如何实现写入磁盘的玩具模型(对于10k大小的挡路，用于简化算术):
- 在磁盘上创建一个10G的文件(它有1000个块)
- 第一个块被指定为根，下一个空闲块被指定为叶，叶地址列表被放入根中
- 插入新数据时，当前叶 node 将填充值，直到达到阈值
- 继续插入数据，将下一个空闲数据分配为叶块，并更新叶 node 列表
- 经过多次插入，当前根 node 需要子 node ，所以下一个空闲的挡路被分配为分支 node ，从根复制列表，现在根只维护一个中间 node 列表.
- 如果需要拆分 node 挡路，则将下一个空闲的挡路分配为分支 node ，添加到根列表中，并在新的分支 node 和初始分支 node 之间拆分叶 node 列表
从大索引中读取信息时:可以执行以下操作:
- 首先阅读/根挡路(查找(0)，读取(10k))，它指向位于挡路900中的子目录
- 阅读挡路900(查找(900*10K)，读取(10K))，它指向位于挡路5000中的子元素
- 阅读挡路5000(查找(5000*10K)，读取(10K))，它指向挡路190中的叶 node
- 读取块190(搜索(190*10k)，读取(10k))并从中提取感兴趣的值
一个非常大的索引可以拆分到多个文件上，那么挡路的地址将是(文件名_id，地址_相对这个文件)