《Oracle Concept》第三章 - 4

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1443858

本文主题：第三章《Indexes and Index-Organized Tables》 - Overview of Indexes。

B树索引

B树索引，是平衡树的缩写，他是数据库索引中最常用的一种类型。一个B树索引是一种将数值有序划分到不同范围的列表。通过将键值和一行或一定范围的行进行关联，B数能为这种范围检索提供极佳的查询性能，包括精确匹配和范围匹配两种检索方式。

下图(3-1)就是B树索引的结构。示例展示了department_id列上的索引，他是employees表的外键。

分支块和叶子块

一个B树索引有两种类型的块：分支块用于检索，叶子块用于存储数值。B树索引上层的分支块会包含指向下层索引块的索引数据。在上图3-1种，根分支块含有0-40的项，他指向了下一层分支块最左侧的块。这个分支块包含了诸如0-10和11-19的项。这些项中的每一个都包含了落在这个范围内指向键值的叶子块。

B树索引是平衡的，因为所有的叶子块都会自动地存储在同一个深度下。因此，从索引中检索任何数据大约花费的时间都是相同的。索引的高度是指需要从根块到叶子块访问的数据块的个数。分支层级等于高度减1。在图3-1中，索引高度是3，分支层级是2。

分支块存储的是需要在两个键值间做权衡中最小的键值前缀。这种技术能让数据库在每个分支块上尽可能多地适应数据。分支块会包含一个指针，他指向包含键值的子块。键和指针的个数受数据块容量的限制。

叶子块则包含每一个被索引的数据值，以及用来定位真实行的rowid。每项会根据(key, rowid)排序。在一个叶子块中，每个键值和rowid都会关联他的左侧和右侧兄弟项。叶子块自己也会双向关联。在图3-1中，最左侧的叶子块(0-10)会关联到第二个叶子块(11-19)。

注意：

字符类型列的索引会基于数据库字符集中的字符二进制值进行排序。