BTreeIndex

BTreeIndex

BTreeIndex使用二叉树数据结构存储。索引的大小随着索引列中不同值的个数而增加。

BTreeIndex利用B+Tree数据结构来允许在调度期间进行过滤。

BTreeIndex与BloomIndex相似，并且对于具有高基数的列非常适用。但是，索引的大小可能会很大，因为索引的大小会随着数量的增加而增加列中独特值的百分比增加。

B+Tree的建立构造使用独特列值作为键，并且可以在其中找到该列值的值。为了减小索引的大小，将为这些值创建一部Dictionary，因此不需要将大型重复项存储多次。

与BloomIndex不同，BTreeIndex还可以使用以下运算符来支持范围查询大于（>），小于（<），BETWEEN等。

使用场景

注意：当前，启发式索引仅支持ORC存储格式的Hive数据源。

BTreeIndex用于调度时的分片(Split)过滤，被coordinator节点使用。

选择适用的列

在具有高基数（即许多独特值）条件的列上具有过滤predicate的queries可以从BTreeIndex中达到好的效果。

例如，类似SELECT FROM FROM users WHERE phone>123456789的query 可以通过在phone列上使用BTreeIndex而达到好的效果，因为列中的数据已被过滤，phone列的基数较高。

在BTreeIndex和BloomIndex索引之间选择时，需要考虑：

BloomIndex只支持=，而BTreeIndex提供范围咨询
BloomIndex是不确定的，而BTreeIndex是确定的。因此BTreeIndex通常有更好的过滤性能
BTreeIndex比BloomIndex索引更大

支持的运算符

=       Equality
>       Greater than
>=      Greater than or equal
<       Less than
<=      Less than or equal
BETWEEN Between range
IN      IN set

支持的列类型

"integer", "smallint", "bigint", "tinyint", "varchar", "double", "real", "date", "decimal"

注意: 不支持采用其它数据类型来创建index。

用例

创建索引:

create index idx using btree on hive.hindex.orders (orderid);
create index idx using btree on hive.hindex.orders (orderid) where orderDate='01-10-2020';
create index idx using btree on hive.hindex.orders (orderid) where orderDate in ('01-10-2020', '01-10-2020');

假设表已按照orderDate列分区

使用索引:

select * from hive.hindex.orders where orderid=12345
select * from hive.hindex.orders where orderid>12345
select * from hive.hindex.orders where orderid<12345
select * from hive.hindex.orders where orderid>=12345
select * from hive.hindex.orders where orderid<=12345
select * from hive.hindex.orders where orderid between 10000 AND 20000
select * from hive.hindex.orders where orderid in (12345, 7890)

如何创建BTreeIndex

BTreeIndex在表级别（table level）（如果表已分区，则在分区级别）创建。

数据作为<Key,Value>对插入。Keys是列值，Values是包含列值的Stripes。对于下面的示例，数据将按以下方式插入：

<"Ant", "/hive/database.db/animals/000.orc+3+1023+12345">  
<"Ant", "/hive/database.db/animals/000.orc+1024+2044+12345">  
<"Ant", "/hive/database.db/animals/001.orc+3+1023+12348">  
<"Crab", "/hive/database.db/animals/000.orc+3+1023+12345">
...

值中包含有关条带的其他信息，以帮助进行过滤并确保不使用陈旧的索引。

由于多次存储长值"/hive/database.db/animals/000.orc+3+1023+12345"会占用太多空间，因此使用了Dictionary。该Dictionary将值映射为整数。而不是存储长字符串值，而是将整数存储在B+Tree中。
随着更多数据的插入，B+Tree重新平衡以确保树的高度不会增加太多，并且查找运行时间保持为O(log(n))。

如何将BTreeIndex用于分片过滤

当OLK引擎需要读取数据时，它会计划分片。每个分片负责读取一部分数据。例如，当读取具有ORC数据格式的Hive表时，每个Split将负责读取指定偏移量之间的ORC文件的一部分。

例如，/hive/database.db/animals/000.orc，起始偏移量0，结束偏移量2000。

对于诸如SELECT * FROM animals WHERE name=Ant;的点查询（point query），通常将需要读取所有数据，并且过滤将仅应用于与predicates匹配的返回行。

通过使用BTreeIndex，只会调度与predicates匹配的分片，因此减少了读取的数据。这样可以大大减少查询的执行时间。

在此示例中，对Ant的BTreeIndex执行查找操作，该操作返回具有以下值的迭代器：

“ /hive/database.db/animals/000.orc+3+1023+12345”
“ /hive/database.db/animals/000.orc+1024+2044+12345”
“ /hive/database.db/animals/001.orc+3+1023+12348”

文件名和偏移量可用于筛选出与predicates不匹配的分片。

此外，上次修改的时间可以用来确保索引仍然有效。如果自创建索引以来已修改原始ORC文件，则索引无效，不应将其用于过滤。

磁盘使用

BTree索引使用磁盘来序列化数据结构。因此，无论是创建BTree索引还是在执行语句时使用BTree索引，都需要本地临时磁盘空间。

对于比较大的表和列，BTree使用的空间可能非常庞大（与列的数据大小相当）。

参见 hindex-statements中的“磁盘使用”章节来指定使用的临时路径。