likes
comments
collection
share

浅谈索引与搜索

作者站长头像
站长
· 阅读数 63

简介

介绍了索引尤其是倒排索引，再通过索引进行搜索。使用倒排索引和调整过滤顺序等手段，优化检索逻辑，避免每次搜索都要遍历所有数据。

文章供6000余字，全文脉络如下：

  • 索引：在MySQL中谈、在Java中谈
  • 倒排索引：在Java中谈、在MySQL中谈、在ES中谈
  • 实践：项目中使用索引加速搜索

2023.1.31目前在找Java后端开发实习岗位。

索引

什么是索引？

当你想查阅书中某个知识的内容，你会选择一页一页的找呢？还是在书的目录去找呢？

傻瓜都知道时间是宝贵的，当然是选择在书的目录去找，找到后再翻到对应的页。书中的目录，就是充当索引的角色，方便我们快速查找书中的内容，所以索引是以空间换时间的设计思想。

那换到数据库中，索引的定义就是帮助存储引擎快速获取数据的一种数据结构，形象的说就是索引是数据的目录。

索引常见面试题 | 小林coding (xiaolincoding.com)

我认为索引是用来加速搜索的，是经典的空间换时间的做法。

MySQL中

MySQL中自动设置主键id字段为主键索引，我们先不论这种索引是怎么实现的（B+树），在执行select * from message where id = ?;时，我们利用额外的空间（创建索引需要空间）来加速搜索。易知主键索引为聚簇索引，即数据与索引放到了一起，我们只利用主键索引搜索，找到了索引就直接拿到了数据。

现在表又有一个conversation_id的字段，这不是主键，MySQL不会为他自动创建索引，但是现在我们需要频繁执行select * from message where conversation_id = ?;，我们考虑给这个字段加索引。因为此字段值不唯一，所以我选择建立普通索引create index index_conversation_id on message(conversation_id);，这是一种非聚簇索引（二级索引），即数据与索引分开存储，执行sql时，先通过普通索引拿到主键值，再通过主键值通过主键索引拿到数据。由于数据与普通索引是完全分离的，可以知道创建普通索引一定会消耗更多的空间，但是达到了加速搜索的目的。

如果conversation_id没有索引我们直接查询会怎样呢？那就会使用全表扫描（type = ALL），效率非常低。使用explain命令查看sql的执行计划，关键信息如下：

mysql> explain select * from message where conversation_id = '111_112';
+----+-------------+---------+------------+------+---------------+------+---------+
| id | select_type | table   | partitions | type | possible_keys | key  | key_len | 
+----+-------------+---------+------------+------+---------------+------+---------+
|  1 | SIMPLE      | message | NULL       | ALL  | NULL          | NULL | NULL    |  
+----+-------------+---------+------------+------+---------------+------+---------+
1 row in set, 1 warning (0.00 sec)

可以看打印的信息中key为NULL。创建普通索引后，再次使用explain命令，关键信息如下：

mysql> explain select * from message where conversation_id = '111_112';
+----+-------------+---------+------------+------+-----------------------+-----------------------+---------
| id | select_type | table   | partitions | type | possible_keys         | key                   | key_len | 
+----+-------------+---------+------------+------+-----------------------+-----------------------+---------
|  1 | SIMPLE      | message | NULL       | ref  | index_conversation_id | index_conversation_id | 137     | 
+----+-------------+---------+------------+------+-----------------------+-----------------------+---------
1 row in set, 1 warning (0.00 sec)

可以看到key为index_conversation_id，说明使用了我们创建的普通索引进行了查询。

MySQL在执行sql查询语句时会经过优化器，详见：执行一条 select 语句，期间发生了什么？ | 小林coding (xiaolincoding.com)

Java中

MySQL了中有张广告内容表，id为主键，其他字段存储了广告的具体内容。如何更快的根据id拿到广告内容呢？我们已经有主键索引了啊。

可以把MySQL数据加载到内存中，在Java中构建索引。我选择使用map数据结构，Map<Integer, AdObject> index，其中key为id，value为广告对象，对象中包含MySQL里一条完整数据。

现在我们再需要根据id拿到广告内容直接index.get(id)就行，你说这是缓存也行，我觉得这个叫索引也没问题，利用了额外空间（内存），达到了加速搜索的目的。

再说之前提到过的conversation_id字段，可以用相同的思路，构建Map<Integer, MessageObject> index，key为conversation_id，value表示MySQL中一条完整数据。

如果我们已经构建了key为id（整条记录的id，即MySQL中的主键），value为MessageObject的索引，上面的这种做法会消耗额外的内存空间，因为我们又存了一份MessageObject。可以使用一种如同MySQL中非聚簇索引的实现，构建Map<Integer, Integer> nonclusteredIndex，其中key为conversation_id，value为主键id。查询时先通过nonclusteredIndex拿到主键id，然后根据主键id拿到MessageObject。不论是哪一种实现，都是通过消耗额外空间，达到加速搜索的目的。

谈hash与索引

Java中里的索引利用了Map数据结构，本质是利用hash连接索引与数据，构建index -> data的映射。那么MySQL为什么不用hash设计索引呢，为什么要使用B+树那么麻烦，感觉hash会比B+树查找的更快。

Hash表必须要有hash算法，这个算法还要足够优秀来保证你的数据能够很好的散列，如果存在大量的hash冲突或者hash碰撞，会导致一部分查询效率非常低 即使算法足够优秀，如果进行范围查询，需要逐一对比每一个元素值，效率很低，并且在生产环境中大部分的查询是范围查询，如果还需要排序那就更低了 hash比较浪费内存空间，而内存是非常宝贵的资源 Mysql 的索引使用的数据结构为什么采用B+Tree，而不采用Hash表、红黑树等其他数据结构_叕叕666的博客-CSDN博客_mysql索引为什么不用hashmap

这里大概有个感觉，后面我们还会详细谈到hash与索引的问题。

倒排索引

以上说的种种我认为都可以归类为正向索引，我们通常所说的索引都是指的正向索引，那么什么是倒排索引呢？

倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)。

倒排索引_百度百科 (baidu.com)

每个学生有至少一个兴趣，现在我们想找兴趣中有游泳的所有学生，该怎么办呢？答：构建一个倒排索引。

我们先构造一个正向索引看看，如下：

02    -> 吃饭
玛奇玛 -> 吃饭、游泳
绫波丽 -> 游泳

此时我们要找兴趣中有游泳的所有学生，就要遍历每个key对应列表里的每个数据，效率低。

倒排索引如下：

吃饭 -> 02、玛奇玛
游泳 -> 玛奇玛、绫波丽

通过游泳可以直接拿到所有兴趣是游泳的学生，如果->表示hash，时间复杂度可以认为是O(1)。

下面通过代码模拟上述找兴趣的情景，索引设计如下：

class Index {
    private Map<String, Set<String>> nameInterestMap = new HashMap<>();//正排索引
    private Map<String, Set<String>> interestNameMap = new HashMap<>();//倒排索引

    public Set<String> getNameSet(String interest) {
        return interestNameMap.get(interest);//从 倒排索引 中取值
    }

    public Set<String> getInterestSet(String name) {
        return nameInterestMap.get(name);//从 正向索引 中取值
    }

    public void set(String interest, Set<String> targetNameSet) {
        //构建倒排索引
        Set<String> nameSet = getOrCreate(interest, interestNameMap, HashSet::new);
        nameSet.addAll(targetNameSet);

        //构建正向索引
        for (String name : targetNameSet) {
            Set<String> interestSet = getOrCreate(name, nameInterestMap, HashSet::new);
            interestSet.add(interest);
        }
    }

    private <K, V> V getOrCreate(K key, Map<K, V> map, Supplier<V> factory) {
        return map.computeIfAbsent(key, k -> factory.get());
    }
}

测试代码如下：

@Test
public void test() {
    Index index = new Index();
    Set<String> eatSet = new HashSet<>();
    eatSet.add("02");
    eatSet.add("玛奇玛");
    Set<String> swimSet = new HashSet<>();
    swimSet.add("玛奇玛");
    swimSet.add("绫波丽");
    invertedIndex.set("吃饭", eatSet);
    invertedIndex.set("游泳", swimSet);

    System.out.println(index.getNameSet("游泳"));
}

index.getNameSet("游泳")利用了倒排索引，结果符合预期，如下：

[玛奇玛, 绫波丽]

当然，想要获取某位同学的兴趣有哪些就更容易了，直接使用正向索引就行，如下

System.out.println(index.getInterestSet("玛奇玛"));
//[吃饭, 游泳]

MySQL中

到此我不禁发问，MySQL中的全文索引（Full Text）使用倒排索引了么？

Mysql的全文索引实际是通过 倒排索引 来实现的。

倒排索引实际就是将要插入的文本按照相应的词进行拆分，然后额外建立一张表，存储这些出现的单词，并做出相应的统计。

Mysql的全文索引原理的简单理解_gttoi的博客-CSDN博客_mysql全文索引原理

5.6之后MySQL自带ngram解析器，可以解析中日韩三国文字，如果不使用ngram解析器，则MySQL默认使用空格与符号作为分隔符（对于英文自然够用了，但对于中日韩文字就不好用了，所以才需要ngram解析器）

【MySQL】全文索引（FULLTEXT）的使用 - 知乎 (zhihu.com)

Auxiliary Table（辅助表）

  • 正如前面所说的，倒排索引需要将word存放到一张表中，这个表称为Auxiliary Table（辅助表）

  • Auxiliary Table是持久的表，存放于磁盘上

FTS Index Cache（全文检索索引缓存）

  • 然而在InnoDB存储引擎的全文索引中，还有另外一个重要的概念**FTS Index Cache（全文检索索引缓存），**其用来提高全文检索的性能
  • FTS Index Cache是一个红黑树结构，其根据（word，ilist）进行排序
  • 这意味着插入的数据已经更新了对应的表，但是对全文索引的更新可能在分词操作后还在FTS Index Cache中，Auxiliary Table可能还没有更新

事务提交时FTS Index Cache的更新

  • 对于InnoDB来说，其总是在事务提交时将分词写入到FTS Index Cache。然后通过批量更新写入到磁盘。虽然InnoDB通过一种延时的、批量的写入方式来提高数据库的性能，但是上述操作仅在事务提交时发生

MySQL(InnoDB剖析):29---全文检索（倒排索引、全文索引/全文检索）_董哥的黑板报的博客-CSDN博客_mysql 倒排索引

通过上面几篇文章的学习，我们了解到MySQL中的全文索引使用了倒排索引，利用辅助表+全文检索索引缓存等手段，加快搜索速度。

谈谈ES

提到倒排索引，我觉得ES是绕不开的话题，反正我认识倒排索引是从ES开始的。

本文不做摘录，希望通读，一定要读。

为什么ElasticSearch比MySQL更适合全文索引 - 腾讯云开发者社区-腾讯云 (tencent.com)

上文涉及两个数据结构：跳表、Bitset，如果不了解可以先看看下面两个小节。

下面罗列一些文章中出现的要点，只能起到帮助阅读的作用，一定要阅读原文。

  • 背景
    • MySQL对于复杂条件的查询支持并不好。
    • ES适合复杂条件查询。
  • 倒排索引
    • 术语：：索引 term、倒排表 posting list。
    • term有序，可以用二分查找，排序后的term称为term dictionary。
    • term dictionary很大，无法直接放入放入内存，这时为了更快的查询，给其建立索引，称为term index。
    • ES使用Burst-Trie（前缀树的变种）构建term index。
    • term index在内存中。
  • 联合索引查询（复杂查询）
    • 根据字段1和字段2进行复杂查询。
      • 由字段1根据term1拿到posting list1。
      • 由字段2根据term2拿到posting list2。
      • posting list1与posting list2取交集。
  • ES的使用跳表和Bitset两种策略优化取交集的过程。
  • 跳表：节约时间
    • 勘误：文中例子里两集合的交集应该为[3,9]而不是[3]。
  • Bitset：节约空间
    • ES会缓存某些posting list到内存。
    • 可以使用Bitset节约内存空间，但Bitset存在稀疏存储的问题。
    • ES使用Roaring Bitmap缓存不同条件查出来的posting list。
  • 后记
    • ES插入慢，且插入后不能立刻搜索到。

补充材料

mysql - 数据库中查询记录时是否每次只能使用一个索引？ - SegmentFault 思否

好用不火 | 比BitMap拥有更好性能的Roaring Bitmap_哔哩哔哩_bilibili

Bitset

提到Bitset，我会先想到Redis中的Bitmap数据结构。

由于 bit 是计算机中最小的单位，使用它进行储存将非常节省空间，特别适合一些数据量大且使用二值统计的场景。

Redis 常见数据类型和应用场景 | 小林coding (xiaolincoding.com)

我们曾使用过他完成网站日活跃用户的统计（DAU），这种场景非常符合上面说的数据量大且是二值统计，我想先简要回顾一下当时是如实现的。

  1. 用拦截器拿到用户id，注意用户id是唯一的。
  2. SETBIT date userId 1，date是表示时间的字符串，表示userId在date访问过我们的网站，他是一名活跃用户。
  3. 统计一段时间内的活跃用户，标准：只要在这段时间访问过一次就是活跃用户。
    • 这段时间中的每一天都有一个Bitmap，Bitmap间使用BITOP进行操作
    • 此场景下我们要做的是进行OR操作，格式：BITOP [operations] [result] [key1] [keyn…]

我们聊了这么多Bitmap，那Bitset到底是什么。其实在Google上搜索，只有Bitmap有wiki词条，而Bitset是有没的，我认为Bitmap（位图）是一种算法思想，只要理解了这种思想，管他什么set还是map其实都不重要吧。

java.util.BitSet 是 JDK 中对 Bitmap 算法的实现类，使用了 long[] 来存储二进制数据。BitSet 提供了 添加、删除、获取数据 以及 与、或、异或 等操作。

深入解析 Bitmap 算法（二）：BitSet - 掘金 (juejin.cn)

In computing, a bitmap is a mapping from some domain (for example, a range of integers) to bits. It is also called a bit array or bitmap index.

Bitmap - Wikipedia

补充材料

java中int类型占4字节，32bit位，最大值2^31-1=2147483647(20多亿)：JDK中的BitSet学习和整理 - 鼠标的博客 - 博客园 (cnblogs.com)

实现DAU统计的第一步有个拦截器拿到用户id，具体是从hostHolder中拿到，而hostHolder中的用户id也是通过拦截器set进去的，这就涉及到拦截器的执行顺序问题，详见：源码分析Spring boot拦截器执行顺序_springboot 拦截器顺序_爱上口袋的天空的博客-CSDN博客

Java 还有一个这么香的工具类，BitSet压缩存储30倍_哔哩哔哩_bilibili

跳表

跳表是对链表的优化，是一种经典的空间换时间的做法，用多余的空间（索引）加速查找。

了解跳表： 学会跳表只需要3分钟 | 让你的链表支持二分查找_哔哩哔哩_bilibili

跳表进阶：Redis中zset数据类型用到了跳表，详见：Redis 数据结构 | 小林coding (xiaolincoding.com)

以后有时间应该详细了解Redis中zset的实现。

再谈hash

从开头到现在，我们说了一大堆。有使用Java编程实现索引，也学习了优秀数据库MySQL和ES中索引的设计，似乎这里有两大流派：哈希表与有序索引。用Java编程时我们使用Map类，是哈希表流；不论是MySQL中的使用B+树构建索引，还是ES中的term dictionary都是有序的，所以他们都是有序索引派。

建议通读这篇文章：Why databases use ordered indexes but programming uses hash tables (evanjones.ca)

我总结要点如下，但还是建议阅读原文。

  • 程序中使用hash更多，DB中使用有序结构更多，但他们都做了一件相同的事：accessing data for our code。
  • MySQL的MEMORY存储引擎支持hash索引，Java中也有TreeMap。
  • 单值时，hashO(1)与树O(logn)；范围问题如“找给定前缀的所有值”“top k”，需要扫描整个hash表。
  • 其他内容请直接阅读原文。

补充阅读

index - Why does MySQL not have hash indices on MyISAM or InnoDB? - Database Administrators Stack Exchange

Hash Index: Everything you Need to Know about Hashing (codingsight.com)

英文资料

There are two types of inverted indexes: A record-level inverted index contains a list of references to documents for each word. A word-level inverted index additionally contains the positions of each word within a document. The latter form offers more functionality, but needs more processing power and space to be created.

Inverted Index - GeeksforGeeks

It is a very important part of information retrieval systems and search engines that stores a mapping of words (or any type of search terms) to their locations in the database table or document.

注意这个mapping。本文还在第四小节介绍了Improving inverted index

What is an inverted index? (educative.io)

搜索

上面同学与兴趣的场景其实就是一种搜索，我们利用倒排索引这种数据结构加速了搜索的过程，倒排索引数据结构是搜素引擎检索算法重要的部分。

在关系型数据库中如MySQL，索引是为了优化查询（搜索）所设计的数据库对象，没有索引也能查，数据库也能用，只是慢。

而如ElasticSearch专用于全文检索数据，倒排索引则是其中的必不可少的部分。

想象一下，有100万篇文章，要求找出含有某个关键字的所有文章，我们只能先分词，然后遍历每一篇文章的每一个词，这是不能接受的。但是我们可以对100万篇文章，根据分词建立倒排索引，通过倒排索引可以一次性拿出含有关键字的所有文章。

实践

项目背景：广告单元有3类需求特征：地区、兴趣、关键词，还有一种广告位信息：流量类型（存储在广告单元对象内）。现在的需求是：给定三种需求特征、流量类型和所有广告单元的id，拿出所有满足要求的广告单元对象。

索引设计：

  • 广告单元：正向索引 | Map<Long, AdUnitObject> objectMap | unitId -> unitObject
  • 关键词：
    • 正向索引 | Map<Long, Set<String>> unitKeywordMap | unitId-> 关键词集合
    • 倒排索引 | Map<String, Set<Long>> keywordUnitMap | 关键词 -> unitId集合
  • 兴趣：同关键词
  • 地区：同关键词

功能实现：

默认索引在添加数据的阶段已经构建完成了，我们要做的工作是搜索。

我们现在有一个Set<Long> allUnitIdSet。

  1. 遍历allUnitIdSet，拿到每一个广告单元对象，判断流量类型是否符合要求，将符合要求的广告单元对象id加入Set<Long> unitIdSet
  2. 过滤出符合关键词要求的广告单元
    • 遍历unitIdSet
      • 拿到unitid
      • 根据unitKeywordMap拿到关键词集合，这一步用到了关键词的正向索引
      • 判断判断我们需求特征中要求的关键词集合是不是刚拿到的关键词集合的子集
      • 不是就将该unitId从unitIdSet中删除
  3. 过滤出符合兴趣要求的广告单元
    • 同关键词的处理
  4. 过滤出符合地区要求的广告单元
    • 同关键词的处理
  5. 返回剩下的unitIdSet集合

高耗时分析：

  • 通过流量类型过滤需要遍历所有unit。foreach()
  • 通过需求特征过滤，需要3次（因为有3种需求特征）遍历上一条中剩下的unit。CollectionUtils.filter()

压力测试：

  • 测试平台：Apifox
  • 数据集：5*2
  • 并发量：50
  • 间隔停顿：10ms
  • 平均接口请求耗时：167ms

优化一

  1. 遍历allUnitIdSet，拿到每一个广告单元对象，判断流量类型是否符合要求，将符合要求的广告单元对象id加入Set<Long> unitIdSet
  2. 新建Set<Long> setByKeyword存储满足关键词的unitId
    • 判断特征需求中关键词列表是否为空
      • 如果为空，setByKeyword = unitIdSet;
      • 如果不为空，遍历关键词列表
        • 拿到关键词
        • 根据倒排索引，由关键词拿到unitId集合，加入setByKeyword
  3. 新建Set<Long> setByInterest存储满足兴趣的unitId
    • 同关键词操作
  4. 新建Set<Long> setByDistrict存储满足地区的unitId
    • 同关键词操作
  5. 返回setByKeyword、setByInterest、setByDistrict的并集

高耗时分析：

  • 通过流量类型过滤需要遍历所有unit。foreach()
  • 需求特征直接通过倒排索引过滤，非高耗时。.get()
  • 求上一条中产生的三个集合的交集。CollectionUtils.intersection()

压力测试：

  • 测试平台：Apifox
  • 数据集：5*2
  • 并发量：50
  • 间隔停顿：10ms
  • 平均接口请求耗时：109ms

优化二

优化一使用倒排索引优化了检索速度，但是在进行第一步（获取满足流量类型要求的所有unitId）时，不论是原来的实现，还是优化一中的实现，都需要遍历所有的unit。我们可以调整过滤顺序，先通过倒排索引过滤三种需求特征，拿到满足需求特征的所有unit，然后再从这些unit中根据流量类型过滤。

先用需求特征过滤，用倒排索引把符合要求的unitId拿出来，然后再这些unitId中选择符合流量类型要求的。

难点：需要处理本来就没有需求特征和有需求特征但是没有符合要求的unit这些特殊情况。

高耗时分析：

  • 由需求特征通过倒排索引直接拿到符合要求的unitId，非高耗时。.get()
  • 随时返回不能满足请求条件的请求，非高耗时，节约执行后续代码的时间。
  • 求上一条中产生的三个集合的交集。CollectionUtils.intersection()
  • 遍历在上一条中产生的集合，根据流量类型过滤。

压力测试：

  • 测试平台：Apifox
  • 数据集：5*2
  • 并发量：50
  • 间隔停顿：10ms
  • 平均接口请求耗时：82ms（相比最初的实现，速度提升100%）

优化三

在数据量大的情况下，使用Bitmap代替Hashset存储unitId，可以节约存储空间，并且节约求交集的时间。

其他

报错：无法自动装配。存在多个 'ISearch' 类型的 Bean

原因：接口ISearch有多个实现类。

@Component("类名")
public class 类名 implements ISearch

@Qualifier("类名")
@Autowired
private ISearch search;

广告单元中的流量类型有开屏广告，Banner广告等。开屏广告支持图标、图片、视频等素材类型，Banner广告支持图标、图片等素材类型。

OPPO广告联盟 (oppomobile.com)

巨量帮助 (oceanengine.com)

腾讯广告 | 广告技术 (qq.com)

广告投放-商业开放平台 (oceanengine.com)

全文检索引擎就是对非结构化文本的进行解析、搜索的技术。非结构化文本处理的关键在于分词与倒排索引。

【IT老齐072】科普向，全文检索执行原理，解释分词与倒排索引的作用_哔哩哔哩_bilibili

最后

没有记录，就没有发生。

完成于2023年2月1日1时07分，全文共6000字。

转载自:https://juejin.cn/post/7194865074073239589
评论
请登录