B树索引与倒排索引的区别?

7

以下是我对两者的理解:

B 树索引:通常用于数据库列中。它将列内容作为键,行 ID 作为值进行保存,并按照排序方式保持键以快速查找键和行位置。

倒排索引:通常用于全文搜索。这里文档中的单词也起到了键的作用,并且按照排序方式存储,同时与文档位置/ID一起保存为值。

那么B树索引和倒排索引之间的区别在哪里呢?我的看法是它们看起来很相似,但实际上有以下不同:

  • B 树索引适用于精确匹配的查询,而倒排索引适用于模糊匹配的查询。
  • B 树索引基于整个关键字进行查找,而倒排索引则基于每个单词进行查找。
  • B 树索引用于数据的插入、更新和删除操作,而倒排索引则主要用于只读操作。
1个回答

16

简短回答:

  • 是的,它们的目的相同 - 快速查找事物
  • 区别在于它们有用/特别擅长的方面
  • 而且命名方式也非常令人困惑

详细回答:

命名

我的知识来自SQL领域的实践,所以对我来说,数据存储就等同于“数据库”,而允许快速查找的结构则是“索引”。

问题在于 - 搜索引擎已经将它们的存储称为“索引”,那么你如何称呼那个“索引”的索引呢?当然是“倒排索引”!为什么是“倒排”?因为正如我在你的问题中看到的那样,它只是将主要存储反转。存储就像主键-->值,辅助结构将其反转为值-->主键,并通过值快速查找文档。

目的

你的问题涉及了一些混合的概念。“倒排索引”实际上更像是“帮助查找已经在存储中的文档的数据结构”,而B-Tree只是这种结构的一种实现。

理论上,可以使用任何你想要的数据结构来实现索引。哈希、图、树、数组、位图等,这取决于您的用例。

区别

B-Tree适用于数据变化频繁的情况,因此它被用于数据库和文件系统中。缺点是多个索引不能在一个查询中同时使用(我猜这是因为该结构是动态的,因此对文档的引用没有排序),并且它的数据往往会散落,因此IO可能会成为问题。

"倒排索引" 使用位图/数组和排序的方式(值列表和对文档的引用列表)。它们适用于静态数据集。由于排序的特性,多个索引可以一起使用。缺点:更新不够高效(新文档意味着在排序列表中插入值),通常采用技巧,将批量数据作为整体保持在一起,并在后台进程中合并成更大的批次。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接