hugegraph图数据库索引详解

前言

在《技术文章之二 hugegraph图数据库概念详解》中我们介绍过IndexLabel,它是索引的元数据,用来描述对顶点/边的属性建立的索引。本文将对hugegraph中的索引做一个较为深入的介绍,并给出每一种索引的适用场景和使用方法的样例。

hugegraph的查询系统是以索引为基础建立的,如果没有索引,hugegraph只能做一些非常简单的查询,比如不带任何条件的查询:g.V()g.E();或者是能够优化为Id查询的条件查询,比如顶点Id策略为PRIMARY_KEY时的主属性(主索引)查询,查询种类十分有限。一旦创建了足够的索引,hugegraph就可以做各种各样复杂的查询了。

hugegraph包含三种索引,分别是:二级索引、范围索引、全文索引,二级索引又可分为单列索引和组合索引,还有一种能联合多种索引的联合索引。给了这么多名次,大家肯定有些头大,不用担心,大家不用太在乎这些索引的名称,暂时知道有多种索引即可,后面阅读完全文,了解这些索引的适用场景和用法即可。

二级索引

二级索引是最常见的索引类型,当用户对某个属性的查询总是“相等”判断时可以使用二级索引二级索引适合建立在大多数普通的属性上,比如:“姓名”、“职业”、“品牌”等容易准确描述的离散值。注意这里的两个措辞:“容易准确描述”和“离散值”并非专业描述,而是用于区别后面的范围索引和全文索引的。

  • “容易准确描述”指用户通常能完整的给出要查找的属性的值,而不是部分的,模糊不清的,比如某人的地址,一大串经常记不住,只能给出“北京市”、“某某小区”这样的部分信息;
  • “离散值”指的是属性的值是一个一个可以罗列的,就像一个一个整数值一样,而不是可以无限细分的浮点数,比如权重、得分这样值。

注意:上面的两个措辞只是一种一般性的描述,可能有些场景下,大的地址已经被限定在“北京市海淀区”里,那地址值就是一些简短的词也不足为奇了,此时也变成了“容易准确描述”的;“离散值”在不同场景下也有不同的定义,所以大家要根据具体的业务场景区分,切勿认死理。

hugegraph中二级索引的逻辑存储结构如下:

field_values | index_label_id | element_ids
  • field_values: 属性的值,可以是单个属性,也可以是多个属性拼接而成
  • index_label_id: 索引标签的Id
  • element_ids: 顶点或边的Id

各种后端具体的“表结构”都按照该逻辑结构设计。

二级索引允许在多个属性上建立索引,在单个属性上建立的索引称为单列索引,在多个属性上建立的索引称之为组合索引,下面分别介绍。

单列索引

先创建一个单列索引标签(元数据):

  1. // 创建索引类型:”personByName”,可以按“name”属性的值快速查询对应的“person”顶点
  2. schema.indexLabel(“personByName”)
  3. .onV(“person”)
  4. .by(“name”)
  5. .secondary()
  6. .create();

再插入几个顶点,有两个顶点的“name”相同:

  1. graph.addVertex(T.label, “person”, T.id, “p1”, “name”, “marko”);
  2. graph.addVertex(T.label, “person”, T.id, “p2”, “name”, “marko”);
  3. graph.addVertex(T.label, “person”, T.id, “p3”, “name”, “josh”);

我们以cassandra后端为例(下同)展示二级索引表的存储结构:

field_values | index_label_id | element_ids
————-±—————±————
marko | 1 | Sp1
marko | 1 | Sp2
josh | 1 | Sp3

表结构中,field_values作为primary key列,index_label_idelement_ids都作为cluster key,这样才能依次存储相同属性的element_id

当用户的查询语句中包含“name”=“marko”这样的条件时,就会命中前面两条记录得到两个element_id,然后再用这两个element_id去顶点表做Id查询得到顶点实体。

在真正的查询流程中,肯定是会先找到index_label_id的,然后用field_valuesindex_label_id一起定位,但是找index_label_id不是这里的重点,一笔带过。

组合索引

先创建一个组合索引标签:

  1. // 创建索引类型:”personByNameAndAge”,可以按“name”和”age”属性的值快速查询对应的“person”顶点
  2. schema.indexLabel(“personByNameAndAge”)
  3. .onV(“person”)
  4. .by(“name”, “age”)
  5. .secondary()
  6. .ifNotExist()
  7. .create();

再插入几个顶点:

  1. graph.addVertex(T.label, “person”, T.id, “p1”, “name”, “marko”, “age”, 29);
  2. graph.addVertex(T.label, “person”, T.id, “p2”, “name”, “vadas”, “age”, 29);
  3. graph.addVertex(T.label, “person”, T.id, “p3”, “name”, “josh”, “age”, 32);

然后再看存储结构:

field_values | index_label_id | element_ids
————-±—————±————
marko | 1 | Sp1
marko | 1 | Sp2
marko!29 | 1 | Sp1
josh!32 | 1 | Sp3
josh | 1 | Sp3
marko!27 | 1 | Sp2

这时我们发现:我只插入了3个顶点,但是一共有6条索引记录,这是为什么呢?

因为组合索引存储时会把多个属性值按顺序拼接在一起作为新的属性值,并且会将该属性值的所有前缀也都存储一份。以第一个顶点为例,它的“name”为“marko”,“age”为29,拼接在一起的新属性值是“marko!29”,会作为一条索引记录存储;然后它的前缀是“marko”,也会存储一份。

以此类推,如果这里创建的属性标签是建立在三个属性上的:“name”、“age”、“city”,假设“city”的值为“Beijing”,那一个顶点会对应三条索引,其field_values分别是“marko”、“marko!29”和“marko!29!Beijing”。

在像rocksdb和hbase这样的后端中,由于rowkey支持前缀匹配,则不会存储这么多的索引记录。

这样的存储结构只提供了前缀匹配的能力,所以当用户查询条件只包含“name”=“marko”时,可以命中前面两条记录;当查询条件包含“name”=“marko”和“age”=29时,可以命中第三条记录;但当查询条件中只包含“age”=29时,则无法命中任何一条记录。所以:创建索引标签时,组合索引中的属性顺序是很重要的。

范围索引

当用户的查询语义是:某属性值大于、小于、大于等于、小于等于、等于某个界限,或者属性值属于某个区间时,适合使用范围索引。比如:“年龄”、“价格”、“得分”等取值比较连续的属性。

要注意的是:该属性必须可以做比较,在Java中也就是实现了Comparable接口,所以Number类型的属性自不必说,像Date这样的属性也是可以创建范围索引的。

hugegraph中二级索引的逻辑存储结构如下:

index_label_id | field_values | element_ids
  • index_label_id: 索引标签的Id
  • field_values: 属性的值,可以是单个属性,也可以是多个属性拼接而成
  • element_ids: 顶点或边的Id

各种后端具体的“表结构”都按照该逻辑结构设计,在cassandra后端中,index_label_id作为primary key列,field_valueselement_ids都作为cluster key。其实相比于二级索引,范围索引表只是将field_valuesindex_label_id调换了一下顺序,这样做是因为在cassandra中,cluster key列是按顺序存储的,而primary key列是哈希存储的。

下面给出一个例子

先创建一个范围索引标签:

  1. // 创建索引类型:”personByAge”,可以按“age”属性的范围快速查询对应的“person”顶点
  2. schema.indexLabel(“personByAge”)
  3. .onV(“person”)
  4. .by(“age”)
  5. .range()
  6. .create();

再插入几个顶点:

  1. graph.addVertex(T.label, “person”, T.id, “p1”, “age”, 29);
  2. graph.addVertex(T.label, “person”, T.id, “p2”, “age”, 27);
  3. graph.addVertex(T.label, “person”, T.id, “p3”, “age”, 32);

然后再看存储结构:

index_label_id | field_values | element_ids
—————±————-±————
1 | 27 | Sp2
1 | 29 | Sp1
1 | 32 | Sp3

可以看到,field_values列的值是按顺序存储的,当用户的查询条件中为“age”>=27 && “age”<30时,可以定位到第一条到第三条记录之间(左闭右开);当查询条件为“age”<29时,可以定位到第一条记录。

全文索引

全文索引用于全文检索,或者说模糊检索,就是用于检索那些“不容易准确描述”的属性值的。比如:“地址”、“描述”等内容很长的属性,全文索引只能对文本类型的属性创建。

hugegraph会使用第三方的分词器将文本切分成多个短词,每个短词分别存储为一条索引记录。查询的时候也会将条件中的词语切分为多个短词,然后每个短词去索引表中查询,最后把每个短词的查询结果取并集就得到了最终的element_ids。全文索引相比于二级索引,只是多个一个分词和将结果合并的步骤,其表结构与二级索引完全相同,这里便不再赘述。

下面给出一个例子

先创建一个全文索引标签:

  1. // 创建索引类型:”personByAddress”,可以根据“address”属性的部分快速查询对应的“person”顶点
  2. schema.indexLabel(“personByAddress”)
  3. .onV(“person”)
  4. .by(“address”)
  5. .search()
  6. .ifNotExist()
  7. .create();

插入几个顶点:

  1. graph.addVertex(T.label, “person”, T.id, “p1”, “address”, “Beijing Haidian Xierqi”);
  2. graph.addVertex(T.label, “person”, T.id, “p2”, “address”, “Shanghai Xuhui”);
  3. graph.addVertex(T.label, “person”, T.id, “p3”, “address”, “Beijing Chaoyang”);

cassandra中的存储结构:

field_values | index_label_id | element_ids
————-±—————±————
shanghai | 1 | Sp2
xuhui | 1 | Sp2
chaoyang | 1 | Sp3
xierqi | 1 | Sp1
haidian | 1 | Sp1
beijing | 1 | Sp1
beijing | 1 | Sp3

可以看到,每个“person”的“address”值都被拆分为了多个部分,比如:“Beijing Haidian Xierqi”被拆分成了“beijing”、“haidian”和“xierqi”,每个单词的首字母还被转换成了小写,但是不影响查询,因为查询的时候也会做同样的转换。

当用户这样查询时:g.V().hasLabel("person").has("address", Text.contains("Beijing"));,分词器会把“Beijing”拆分(转换)为“beijing”,然后命中两条记录;当使用g.V().hasLabel("person").has("address", Text.contains("Beijing Shanghai"));查询时,分词器会把“Beijing Haidian”拆分为“beijing”和“shanghai”,其中“beijing”能命中两条记录“Sp1”和“Sp3”,“shanghai”能命中“Sp2”,然后取并集得到“Sp1”、“Sp2”和“Sp3”。

联合索引

上面提到的索引和查询都是独立工作的,就是说一个查询只会涉及到一个索引类型(IndexLabel),比如示例中:根据“name”=“xxx”查“person”时只会涉及到“personByName”这一个二级索引;根据“age”>xxx查“person”时只会涉及到“personByAge”这一个范围索引;即使是在传入多个条件的二级索引(组合索引)和通过分词产生多条件的全文索引中,也只会涉及到各自的单个索引,即“personByNameAndAge”和“personByAddress”。

相信看到这里,大家会有两个疑惑:

  • 单独创建多个单列索引和创建一个组合索引有什么区别?比如创建两个单列索引:“personByName”、“personByAge”,和创建一个组合索引:“personByNameAndAge”会对查询产生怎样的影响。
  • 似乎只有组合索引支持多个条件的查询,而且组合索引只提供了前缀匹配的能力,那岂不是要将所有的属性排列组合都创建为索引,才能支持任意属性的查询?

其实这两个问题是有关联的,可以合并为一个问题。单独创建多个单列索引和创建一个组合索引的区别在于:单独创建多个单列索引既支持单个属性的查询,也支持多个属性的组合查询,而组合索引只支持前缀属性的查询。

就以“personByName”、“personByAge”和“personByNameAndAge”为例,“personByName”、“personByAge”支持通过“name”查,支持通过“age”查,也支持通过“name”和“age”一起查;但是“personByNameAndAge”只支持通过“name”查和通过“name”和“age”一起查,不支持作为后缀的“age”查。

那多个单列索引是如何支持多个属性的组合查询的呢?很简单,依次查询然后将结果取交集,如果交集为空,则停止查询(这里所说的查询是指查询索引表),这种索引模式称为联合索引。

那又有人问了,既然组合索引能做的联合索引都能做,组合索引的意义何在呢?其实稍微一下就能知道:组合索引提供了前缀匹配的能力,在多属性查询时,一次查询就能命中,而联合查询则需要做最多N(属性个数)次查询,明显组合索引效率更高。所以,大家要根据具体的业务场景创建好索引,如果某些属性经常要组合在一起查询,最好把它创建为组合索引。

下面给出一个例子

先创建几个索引标签:

  1. // 创建组合索引:”personByNameAndAge”,可以根据“name”、“name”+“age”快速查询对应的“person”顶点
  2. schema.indexLabel(“personByNameAndAge”)
  3. .onV(“person”)
  4. .by(“name”, “age”)
  5. .secondary()
  6. .create();
  7. // 创建范围索引:”personByAge”,可以根据“age”属性的范围查询对应的“person”顶点
  8. schema.indexLabel(“personByAge”)
  9. .onV(“person”)
  10. .by(“age”)
  11. .range()
  12. .create();
  13. // 创建全文索引:”personByAddress”,可以根据“address”属性的部分快速查询对应的“person”顶点
  14. schema.indexLabel(“personByAddress”)
  15. .onV(“person”)
  16. .by(“address”)
  17. .search()
  18. .ifNotExist()
  19. .create();

插入几个顶点:

  1. graph.addVertex(T.label, “person”, T.id, “p1”, “name”, “marko”, “age”, 29, “address”, “Beijing Haidian Xierqi”);
  2. graph.addVertex(T.label, “person”, T.id, “p2”, “name”, “marko”, “age”, 27, “address”, “Shanghai Xuhui”);
  3. graph.addVertex(T.label, “person”, T.id, “p3”, “name”, “josh”, “age”, 32, “address”, “Beijing Chaoyang”);

存储结构就不看了,我们直接来做查询:

  1. // 通过“personByNameAndAge”做前缀匹配,命中“p1”和“p2”
  2. g.V().hasLabel(“person”).has(“name”, “marko”).toList();
  3. // 通过“personByNameAndAge”做前缀匹配(全匹配),命中“p1”
  4. g.V().hasLabel(“person”).has(“name”, “marko”).has(“age”, 29).toList();
  5. // 通过“personByNameAndAge”做前缀匹配(全匹配),命中“p1” ,从这里看出,查询时属性的顺序无影响
  6. g.V().hasLabel(“person”).has(“age”, 29).has(“name”, “marko”).toList();
  7. // 通过“personByAge”做范围查询,命中“p1”和“p2”
  8. g.V().hasLabel(“person”).has(“age”, P.between(27, 30)).toList();
  9. // 通过“personByAddress”做全文检索,命中“p1”和“p3”
  10. g.V().hasLabel(“person”).has(“address”, Text.contains(“Beijing”)).toList();
  11. // 通过“personByNameAndAge”和“personByAddress”做联合索引查询,命中“p1”
  12. g.V().hasLabel(“person”).has(“name”, “marko”).has(“address”, Text.contains(“Beijing”)).toList();
  13. // 通过“personByAge”和“personByAddress”做联合索引查询,命中“p1”
  14. g.V().hasLabel(“person”).has(“age”, P.between(27, 30)).has(“address”, Text.contains(“Beijing”)).toList();

 

 

授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!

发表评论

电子邮件地址不会被公开。 必填项已用*标注


*