HBASEB+树索引谭波波.pdf

HBASE-B+树索引-谭波波

记录：谭波波

1.索引结构

1.1B+树索引结构

从物理上说，索引通常可以分为：分区和非分区索引、常规B树索引、位图（bitmap）索引、翻转

（reverse）索引等。其中，B树索引属于最常见的索引

B树索引是一个典型的树结构，其包含的组件主要是：

叶子节点（Leafnode）：包含条目直接指向表里的数据行。

分支节点（Branchnode）：包含的条目指向索引里其他的分支节点或者是叶子节点。

根节点（Rootnode）：一个B树索引只有一个根节点，它实际就是位于树的最顶端分支节点。

可以用下图一来描述B树索引的结构。其中，B表示分支节点，而L表示叶子节点。

对于分支节点块（包括根节点块）来说，其所包含的索引条目都是按照顺序排列的（缺省是升序排列，

也可以在创建索引时指定为降序排列）。每个索引条目（也可以叫做每条记录）都具有两个字段。第一个字

段表示当前该分支节点块下面所链接的索引块中所包含的最小键值；第二个字段为四个字节，表示所链接的

索引块的地址，该地址指向下面一个索引块。

在一个分支节点块中所能容纳的记录行数由数据块大小以及索引键值的长度决定。

对于叶子节点块来说，其所包含的索引条目与分支节点一样，都是按照顺序排列的（缺省是升序排列，

也可以在创建索引时指定为降序排列）。每个索引条目（也可以叫做每条记录）也具有两个字段。第一个字

段表示索引的键值，对于单列索引来说是一个值；而对于多列索引来说则是多个值组合在一起的。第二个字

段表示键值所对应的记录行的ROWID，该ROWID是记录行在表里的物理地址。如果索引是创建在非分区表上或

者索引是分区表上的本地索引的话，则该ROWID占用6个字节；如果索引是创建在分区表上的全局索引的话，

则该ROWID占用10个字节

1.2估算索引条目

对于每个索引块来说，缺省的PCTFREE为10％，也就是说最多只能使用其中的90％。同时9i后，这90％

中也不可能用尽，只能使用其中的87％左右。也就是说，8KB的数据块中能够实际用来存放索引数据的

空间大约为6488（8192×90％×88％）个字节

假设我们有一个非分区表，表名为warecountd，其数据行数为130万行。该表中有一个列，列名为goodid，其

类型为char（8），那么也就是说该goodid的长度为固定值：8。同时在该列上创建了一个B树索引

在叶子节点中，每个索引条目都会在数据块中占一行空间。每一行用2到3个字节作为行头，行头用来存放标

记以及锁定类型等信息。同时，在第一个表示索引的键值的字段中，每一个索引列都有1个字节表示数据长

度，后面则是该列具体的值。那么对于本例来说，在叶子节点中的一行所包含的数据大致如下图二所示：

从上图可以看到，在本例的叶子节点中，一个索引条目占18个字节。同时我们知道8KB的数据块中真正可以用

来存放索引条目的空间为6488字节，那么在本例中，一个数据块中大约可以放360（6488/18）个索引条目

而对于我们表中的130万条记录来说，则需要大约3611（1300000/360）个叶子节点块

而对于分支节点里的一个条目（一行）来说，由于它只需保存所链接的其他索引块的地址即可，而不需要保

存具体的数据行在哪里，因此它所占用的空间要比叶子节点要少。分支节点的一行中所存放的所链接的最小

键值所需空间与上面所描述的叶子节点相同；而存放的索引块的地址只需要4个字节，比叶子节点中所存放

的ROWID少了2个字节，少的这2个字节也就是ROWID中用来描述在数据块中的行号所需的空间。因此，本例中

在分支节点中的一行所包含的数据大致如下图三所示：

从上图可以看到，在本例的分支节点中，一个索引条目占16个字节。根据上面叶子节点相同的方式，我们可

以知道一个分支索引块可以存放大约405（6488/16）个索引条目。而对于我们所需要的3611个叶子节点来

说，则总共需要大约9个分支索引块。

这样，我们就知道了我们的这个索引有2层，第一层为1个根节点，第二层为9个分支节点，而叶子节点数

为3611个，所指向的表的行数为1300000行。但是要注意，在oracle的索引中，层级号是倒过来的，也就是说

假设某个索引有N层，则根节点的层级号为N，而根节点下一层的分支节点的层级号为N-1，依此类推。对本例

来说，9个分支节点所在的层级号为1，而根节点所在的层级号为2。

2.B+树索引的管理机制

2.1B+树索引