Elasticsearch 是一个基于 Lucene 构建的分布式、RESTful 风格的搜索和数据分析引擎。它通过有限状态转换器实现了用于全文检索的倒排索引、用于存储数值数据和地理位置数据的 BKD 树,以及用于分析的列存储。
REST:Representational State Transfer,表现层状态转化。是一种软件架构风格,没有严格的定义,侧重于识别资源。
REST 其实不难理解。简单来说,即表现层的 HTTP 动词和状态码发生变化,以 GET、POST、PUT、DELETE 等来明确描述对资源的操作,并能通过状态码获得请求的状态。
RESTful API 是遵循 REST 架构风格的 Web API。它使用 URI 来标识资源,且每个 URI 代表一种资源。
一般API:
POST /user/list // 获取列表
POST /user/get // 获取
POST /user/add // 添加
POST /user/edit // 编辑
POST /user/delete // 删除
RESTful API:
GET /user // 获取列表
GET /user/{id} // 获取
POST /user // 添加
PUT /user/{id} // 编辑
DELETE /user/{id} // 删除
实例,
其实这就是一种潜移默化的 API 设计风格,看了下知乎和腾讯云社区 API 都有 RESTful 的倾向。但 RESTful API 不适用于复杂请求逻辑,需选择性使用。
倒排索引
常规的索引是文档到关键词的映射:
文档 ——> 关键词
但这样检索关键词的时候很费力,要遍历文档。于是有了倒排索引。
倒排索引是关键词到文档的映射:
关键词 ——> 文档
举例,
① —> what is elasticsearch used for
② —> what is elasticsearch index
③ —> inverted index in elasticsearch
Inverted Index
Term | TF | Posting List |
---|---|---|
what | 2 | [1, 2] |
is | 2 | [1, 2] |
elasticsearch | 3 | [1, 2, 3] |
used | 1 | [1] |
for | 1 | [1] |
index | 2 | [2, 3] |
inverted | 1 | [3] |
in | 1 | [3] |
注:
TF,Term Frequency
分词,即将一个文本拆分成单个Term
Posting List,倒排列表。记录了出现过某个单词的文档列表,及单词在该文档中的位置信息
如果这时候搜索 elasticsearch inverted index,先找到对应 term
Term | TF | Posting List |
---|---|---|
elasticsearch | 3 | [1, 2, 3] |
index | 2 | [2, 3] |
inverted | 1 | [3] |
将 Posting List 转化成 Bitset
[1, 2, 3] —> 111
[2, 3] —> 011
[3] —> 001
然后按位与得到001,即 ③ inverted index in elasticsearch 匹配度更高。实际应用中,还会考虑单词大小写、同义词、拼写错误等问题。而这些是普通关系数据库很难做到的。
有限状态转换器,Elasticsearch 通过有限状态转换器实现倒排索引。
主要作用:对单词前缀及后缀重复利用,压缩存储空间
区别:TRIE 树只共享前缀
一般来说,生成 FST 需要保证单词字典序顺序。
例:
he/0
hey/1
on/2
one/3
org/4
tag/5
其中灰色边指向的节点为输出节点如 on。示例单词共享前缀 h、o,共享后缀 g。
推荐阅读:
Lucene FST_zouxiang_1993的博客-CSDN博客_fst lucene
关于Lucene的词典FST深入剖析 | 申艳超-博客 (shenyanchao.cn)
一种数据结构,用于存储数据并搜索处理等。
k-dimensional tree,k 维树,是一种 k 维空间分区数据结构。k-d 树是一个二叉树,其中每个节点都是一个 k 维点。
三维:
二维:
有多种方法构建 k-d 树,其中较为典型的是:层级按 k 维循环划分;子树由分割面中点的相对中位数进行拆分。
如:x —> y —> x —> y —> x ...
x —> y —> z —> x —> y —> z —> x ...
例:以上述二维 k-d 树举例
红线以 x 维度划分,蓝线以 y 维度划分。坐标:(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)
① 以 x 为维度,找到中间值作为根节点,即 (7,2)。此时平面以 x = 7 为分割线,分为两个平面
② 在 (7,2) 的两侧平面,以 y 为维度,找到相对中位数点,并放入左右子树
③ 再以 x 维度进行划分
注:不是一定要选择子树中的中位数点进行平面拆分。如果未选择中位数点,则无法保证树平衡。一种常规做法是不对子树中的所有点进行排序,而是对固定数量的随机选择的点进行排序,并使用这些点的中位数作为拆分平面。在实践中,这种做法通常会产生较为平衡的树。
k-dimensional B-tree,k 维 B 树。k-d-b 树的目的是提供平衡的 k-d 树的搜索效率,同时提供 B 树的面向块的存储,以优化外部存储器访问。
k-d-b 树是 k-d 树和 B 树的结合。它将不同区域 k-d 树作为整体放在 B 树里。
kdb 树包含两种类型的页面:
Region pages:(区域、子树) 对的集合,其中包含区域边界的说明,以及该区域对应子页面的指针。
Point pages:(点、位置) 对的集合。
插入数据的过程中 k-d 树可能会不平衡,甚至出现二叉树退化成链表的情况。此时需要进行重建 k-d 树等操作,开销过大。
k-d-b树可以改善该问题,但局部区域k-d树仍可能退化,且拆分页面时很可能会涉及多个子区域。
故相比于k-d树,k-d-b树对于修改频繁的动态数据存储效率并没有多大改善。两者都较适用于分析静态数据。
设 N 是点的总数,B 是磁盘里的点数, K 是查询矩形中的点数。M 是内存缓冲区的容量,以点数表示
If N is the total number of points and B is the number of points that fit in a disk block.....Here K is the number of points in the query rectangle.
M is the capacity of the memory buffer, in number of points.
bkd 树由一组平衡的 kd 树组成。每个 kd 树在磁盘上的布局类似于 kdb 树的布局方式。
bkd 树和 kdb 树主要的不同主要存在于两个方面:批量构建 及 动态更新。
上图描述了两种批量构建 kd 树的算法,一般来说 kd 树是以二进制 binary 自上而下构建的。基于 x、y 维度创建排序列表,并以深度优先搜索插入每个节点。
但是 bkd 树采取了 grid 构建方式,基于论文 P. K. Agarwal, L . Arge, O. Procopiuc, and J. S. Vitter. A framework for index bulk loading and dynamization. In Proc. Intl. Colloq. Automata, Languages and Programming, pages 115–127, 2001.
它同样需要先创建排序列表,先构建 kd 树的 log_2t 层,其中 t = Θ(min{M/B, √M}).,然后递归构建。
最后发现 grid 的复杂度比 binary 好 Θ(log_2(M/B)) 。实验结果表明 gird I/Os 优于 binary 批量构建方式。
平面中 N 个点的 Bkd 树,由 log_2(N/M) 个 kd 树组成。内存中保存了这些最多包含 2^i M 个点的结构 T^M。而在外部存储中,第 T_i 个 kd 树要么是空的,要么恰好包含 2^i M 个点。
主要看一下插入算法。点插入 buffer 里的结构 T^M,若 T^M 未满,则直接插入。若 T^M 满,则找到外部存储的第一棵空 kd 树 T_k,将 T^M 和所有 T_i 中的点批量构建进去。最后清空 T^M 和 T_i,0 ≤ i < k.
清空了 T_i,那么下次重组可用的第一棵空树就是 T_i。比如要构建 T_2,那么他的前提是 T^M、T_0、T_1 都已经满了。而构建了 T_2 之后,会清空 T_0、T_1,下次重组又会从 T_0 重新开始。这样就可以实现树的大小以 2^i 的规律增长。
换句话说,点存储到内存中,并定时重组到外部存储。kd-tree 越大,需要重组的频率就越低。
这个数据结构被 Lucene6.0 之后版本用于索引多维数值类型的数据,具体代码可以查看 org.apache.lucene.util.bkd (Lucene 7.1.0 API)
该论文的实验结果表明,Bkd 树的空间利用率高达 99%,而 KDB 树空间利用率只有 30%~50% 左右不等。Bkd 树中的插入比 KDB 树中的插入快 100 倍左右,查询等性能也表现更好。
还是回到了文章的开头:
Elasticsearch 是一个基于 Lucene 构建的分布式、RESTful 风格的搜索和数据分析引擎。它通过有限状态转换器实现了用于全文检索的倒排索引、用于存储数值数据和地理位置数据的 BKD 树,以及用于分析的列存储。
参考:
Elasticsearch:官方分布式搜索和分析引擎 | Elastic
Api接口风格 - 腾讯云开发者社区-腾讯云 (tencent.com)
带你走进神一样的Elasticsearch索引机制 - 知乎 (zhihu.com)
elasticsearch 倒排索引原理 - 知乎 (zhihu.com)
倒排索引为什么叫倒排索引? - 知乎 (zhihu.com)
lucene字典实现原理 - zhanlijun - 博客园 (cnblogs.com)
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。