浅谈索引与搜索

水深无声 2023-10-04 20:39 60阅读 0赞

## 简介 ##

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

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

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

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

## 索引 ##

什么是索引？

> 当你想查阅书中某个知识的内容，你会选择一页一页的找呢？还是在书的目录去找呢？
> 
> 傻瓜都知道时间是宝贵的，当然是选择在书的目录去找，找到后再翻到对应的页。书中的**目录**，就是充当**索引**的角色，方便我们快速查找书中的内容，所以索引是以空间换时间的设计思想。
> 
> 那换到数据库中，索引的定义就是帮助存储引擎快速获取数据的一种数据结构，形象的说就是**索引是数据的目录**。
> 
> [索引常见面试题 | 小林coding (xiaolincoding.com)][_ _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的执行计划，关键信息如下：

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

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

MySQL在执行sql查询语句时会经过**优化器**，详见：[执行一条 select 语句，期间发生了什么？ | 小林coding (xiaolincoding.com)][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][Mysql _B_Tree_Hash_666_-CSDN_mysql_hashmap]

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

## 倒排索引 ##

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

> 倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)。
> 
> [倒排索引\_百度百科 (baidu.com)][_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的[全文索引][Link 1]实际是通过 **倒排索引** 来实现的。
> 
> **倒排索引实际就是将要插入的文本按照相应的词进行拆分，然后额外建立一张表，存储这些出现的单词，并做出相应的统计。**
> 
> [Mysql的全文索引原理的简单理解\_gttoi的博客-CSDN博客\_mysql全文索引原理][Mysql_gttoi_-CSDN_mysql]

> 5.6之后MySQL自带ngram解析器，可以解析中日韩三国文字，如果不使用ngram解析器，则MySQL默认使用空格与符号作为分隔符（对于英文自然够用了，但对于中日韩文字就不好用了，所以才需要ngram解析器）
> 
> [【MySQL】全文索引（FULLTEXT）的使用 - 知乎 (zhihu.com)][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_InnoDB_29---_-CSDN_mysql]

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

### 谈谈ES ###

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

> 本文不做摘录，希望**通读**，一定要读。
> 
> [为什么ElasticSearch比MySQL更适合全文索引 - 腾讯云开发者社区-腾讯云 (tencent.com)][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 思否][mysql - _ - SegmentFault]
> 
> [好用不火 | 比BitMap拥有更好性能的Roaring Bitmap\_哔哩哔哩\_bilibili][_ _BitMap_Roaring Bitmap_bilibili]

#### Bitset ####

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

> 由于 bit 是计算机中最小的单位，使用它进行储存将非常节省空间，特别适合一些数据量大且使用**二值统计的场景**。
> 
> [Redis 常见数据类型和应用场景 | 小林coding (xiaolincoding.com)][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)][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)][JDK_BitSet_ - _ - _ _cnblogs.com]
> 
> 实现DAU统计的第一步有个拦截器拿到用户id，具体是从hostHolder中拿到，而hostHolder中的用户id也是通过拦截器set进去的，这就涉及到拦截器的执行顺序问题，详见：[源码分析Spring boot拦截器执行顺序\_springboot 拦截器顺序\_爱上口袋的天空的博客-CSDN博客][Spring boot_springboot _-CSDN]
> 
> [Java 还有一个这么香的工具类，BitSet压缩存储30倍\_哔哩哔哩\_bilibili][Java _BitSet_30_bilibili]

#### 跳表 ####

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

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

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

以后有时间应该详细了解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)][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][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)][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)][What is an inverted index_ _educative.io]

## 搜索 ##

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

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

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

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

### 实践 ###

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

**索引设计**：

**功能实现**：

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

我们现在有一个`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()`

### 优化一 ###

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()`

### 优化二 ###

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

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

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

**高耗时分析**：

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

### 优化三 ###

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

## 其他 ##

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

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

@Component("类名")
    public class 类名 implements ISearch
    复制代码

@Qualifier("类名")
    @Autowired
    private ISearch search;
    复制代码

--------------------

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

作者：带姬仔  
原文链接：https://juejin.cn/post/7194865074073239589

[_ _coding _xiaolincoding.com]: https://link.juejin.cn?target=https%3A%2F%2Fxiaolincoding.com%2Fmysql%2Findex%2Findex_interview.html%23%25E4%25BB%2580%25E4%25B9%2588%25E6%2598%25AF%25E7%25B4%25A2%25E5%25BC%2595
[select _ _ _coding _xiaolincoding.com]: https://link.juejin.cn?target=https%3A%2F%2Fxiaolincoding.com%2Fmysql%2Fbase%2Fhow_select.html%23%25E4%25BC%2598%25E5%258C%2596%25E5%2599%25A8
[Mysql _B_Tree_Hash_666_-CSDN_mysql_hashmap]: https://link.juejin.cn?target=https%3A%2F%2Fblog.csdn.net%2Fm0_50163856%2Farticle%2Fdetails%2F123633138
[_baidu.com]: https://link.juejin.cn?target=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E5%2580%2592%25E6%258E%2592%25E7%25B4%25A2%25E5%25BC%2595
[Link 1]: https://link.juejin.cn?target=https%3A%2F%2Fso.csdn.net%2Fso%2Fsearch%3Fq%3D%25E5%2585%25A8%25E6%2596%2587%25E7%25B4%25A2%25E5%25BC%2595%26spm%3D1001.2101.3001.7020
[Mysql_gttoi_-CSDN_mysql]: https://link.juejin.cn?target=https%3A%2F%2Fblog.csdn.net%2Fqq_38046325%2Farticle%2Fdetails%2F123183734
[MySQL_FULLTEXT_ - _ _zhihu.com]: https://link.juejin.cn?target=https%3A%2F%2Fzhuanlan.zhihu.com%2Fp%2F417229576
[MySQL_InnoDB_29---_-CSDN_mysql]: https://link.juejin.cn?target=https%3A%2F%2Fblog.csdn.net%2Fqq_41453285%2Farticle%2Fdetails%2F104251526
[ElasticSearch_MySQL_ - _-_ _tencent.com]: https://link.juejin.cn?target=https%3A%2F%2Fcloud.tencent.com%2Fdeveloper%2Farticle%2F1789751
[mysql - _ - SegmentFault]: https://link.juejin.cn?target=https%3A%2F%2Fsegmentfault.com%2Fq%2F1010000003880137
[_ _BitMap_Roaring Bitmap_bilibili]: https://link.juejin.cn?target=https%3A%2F%2Fwww.bilibili.com%2Fvideo%2FBV1Dt4y1M7dY%2F
[Redis _ _ _coding _xiaolincoding.com]: https://link.juejin.cn?target=https%3A%2F%2Fxiaolincoding.com%2Fredis%2Fdata_struct%2Fcommand.html%23bitmap
[Bitmap _BitSet - _ _juejin.cn]: https://juejin.cn/post/6972395594686054414
[computing]: https://link.juejin.cn?target=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FComputing
[bits]: https://link.juejin.cn?target=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FBit
[bit array]: https://link.juejin.cn?target=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FBit_array
[bitmap index]: https://link.juejin.cn?target=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FBitmap_index
[Bitmap - Wikipedia]: https://link.juejin.cn?target=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FBitmap
[JDK_BitSet_ - _ - _ _cnblogs.com]: https://link.juejin.cn?target=https%3A%2F%2Fwww.cnblogs.com%2Fyb38156%2Fp%2F16544516.html
[Spring boot_springboot _-CSDN]: https://link.juejin.cn?target=https%3A%2F%2Fblog.csdn.net%2FK_520_W%2Farticle%2Fdetails%2F124529633
[Java _BitSet_30_bilibili]: https://link.juejin.cn?target=https%3A%2F%2Fwww.bilibili.com%2Fvideo%2FBV1Da4114769%2F
[3_ _ _bilibili]: https://link.juejin.cn?target=https%3A%2F%2Fwww.bilibili.com%2Fvideo%2FBV1QK4y1Y7mS%2F
[Redis _ _ _coding _xiaolincoding.com 1]: https://link.juejin.cn?target=https%3A%2F%2Fxiaolincoding.com%2Fredis%2Fdata_struct%2Fdata_struct.html%23%25E8%25B7%25B3%25E8%25A1%25A8
[Why databases use ordered indexes but programming uses hash tables _evanjones.ca]: https://link.juejin.cn?target=https%3A%2F%2Fwww.evanjones.ca%2Fordered-vs-unordered-indexes.html
[index - Why does MySQL not have hash indices on MyISAM or InnoDB_ - Database Administrators Stack Exchange]: https://link.juejin.cn?target=https%3A%2F%2Fdba.stackexchange.com%2Fquestions%2F2817%2Fwhy-does-mysql-not-have-hash-indices-on-myisam-or-innodb
[Hash Index_ Everything you Need to Know about Hashing _codingsight.com]: https://link.juejin.cn?target=https%3A%2F%2Fcodingsight.com%2Fhash-index-understanding-hash-indexes%2F
[Inverted Index - GeeksforGeeks]: https://link.juejin.cn?target=https%3A%2F%2Fwww.geeksforgeeks.org%2Finverted-index%2F
[What is an inverted index_ _educative.io]: https://link.juejin.cn?target=https%3A%2F%2Fwww.educative.io%2Fanswers%2Fwhat-is-an-inverted-index