Interview preparation--elasticSearch倒排索引原理

2024-06-23 14:04
文章标签 interview preparation elasticsearch 倒排 索引 原理

本文主要是介绍Interview preparation--elasticSearch倒排索引原理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

搜索引擎应该具备哪些要求
  • 查询速度快
    • 优秀的索引结构设计
    • 高效率的压缩算法
    • 快速的编码和解码速度
  • 结果准确
    • ElasiticSearch 中7.0 版本之后默认使用BM25 评分算法
    • ElasticSearch 中 7.0 版本之前使用 TP-IDF算法
倒排索引原理
  • 当我们有如下列表数据信息，并且系统数据量达到10亿，100亿级别的时候，我们系统该如何去解决查询速度的问题。
  • 数据库选择—mysql， sybase，oracle，mongodb，唯一加速查询的方法是添加索引
索引
  • 无论哪一种存储引擎的索引都是如下几个特点
    • 帮助快速检索
    • 以数据结构为载体
    • 以文件的形式落地
  • 如下图中mysql的文件形式，其中的idb文件就是使用innodb存储引擎来实现数据存储生成的文件，其他后缀的文件是其他存储引擎生成的，因此无论什么引擎，索引方式，数据结构最终都是要落文件的

在这里插入图片描述

  • 传统数据库的基本结构如下：

在这里插入图片描述

  • MySql包括Server层和存储引擎层：Server层包括，连接器，查询缓存，分析器，优化器，执行器
  • 连接器：负责和客户端建立连接
  • 查询缓存：MySql获取到查询请求后，会先查询缓存，如果之前已经执行过一样的语句结果会以Key-value的形式存储到内存中，key是查询语句，value是查询结果。缓存明中的话可以很快完成查询，但是大多是情况不能明中，不建议用缓存，因为缓存失效非常频繁，任何对表的更新都会让缓存晴空，所以对一个进程更改的表而言，查询缓存基本不可用，除非是一张配置表。可以通过配置来决定释放开启查询缓存，并且MySql8.0 之间删除了查询缓存功能
  • 分析器：词法分析，识别语句中表名，列名，语法分析，判断Sql是否满足MySql语法
  • 优化器：在有多个索引的情况下，决定使用哪个索引，或者多表联合查询的时候，表的连接顺序这么执行等
  • 执行器：执行器先判断权限，有权限才会去调用存储引擎对应的查询接口，默认InnoDB
数据载体 mongodb & mysql
  • 以为mongodb为案例，索引数据存储的结构如下

在这里插入图片描述

  • Mongodb索引使用的是B树：B树是多叉平衡查找树，包括以下几个结构特性

    • 左子树数据小于跟数据，右子树数据大于根节点数据
    • 左右子树高度差不大于1
    • 每个节点可以有N个字节的，N>2

  • B树的每个节点都存放 索引 & 数据，数据遍布整个树结构，搜索可能在非叶子结点结束，最好情况是O(1)

  • B树存在的问题：

    • 紫色部分存储数据的主键信息，蓝色存储的是指针指向下一个节点，黄色部分是存储的主键对应的数据Data。因此Data是在节点中占比最大的一部分数据，他可能有1M或者更大的一个数据体
    • 假设我们一个节点的大小是固定的M，在Mysql中最小的数据逻辑单元是数据页，一个数据页是16KB，如果Data越大，M所能容纳的Data个数就越小就导致存储更多的数据久需要更多的节点，B树为了承载更多的节点为了满足结构特性就需要更多的分叉，因此就导致树的深度更大，每一个层级都意味着一次IO操作导致IO次数更多

  • 以为Mysql为案例分析：

在这里插入图片描述

  • Mysql中innoDB 使用的索引结构是B+树，
  • B+ 树是B树的变种，区别在于：
    • 叶子结点保存了完整的索引 & 数据，非叶子结点只保存索引值，因此他的查询时间固定为logn
    • 叶子结点中有指向下一个叶子结点的指针，叶子结点类似一个双向链表
    • 因为叶子结点有完整数据，并且有双链表结构，因此我们在范围查询的时候能有效提升查询效率。
  • 数据都在子节点上，因此非自节点就能容纳更多的索引信息，这样就增加了同一个节点的出度，减少了数据信息，同一个节点久能容纳更多的数据信息，因此能用更少的节点来完成所有数据的索引存储，节点的减少导致减少了树的深度，查询的IO次数就变少了。
倒排索引数据结构
  • 对如上两个索引结构的分析，我们能看到MySql 无法解决大数据索引问题：
    • 第一点：索引往往字段很长，如果使用B+trees，树可能很深，IO很可怕
    • 第二点：索引可能会失效
    • 第三点：查询准确度差，
  • 有如下案例，有1亿条数据的商品信息，我们需要对其中的product字段进行查询，而且是文本信息查询，例如“小米”这个字段查询，那么有如下查询语句：
select * from product where brand like "%小米 NFC 手机%"

  • 第一点说明：以上查询语句，我们需要在product上建索引， MySql上使用的B+树，因为文本的信息量特别的大，导致所需要的节点就更多N个16KB（MySql索引中如果一个数据行的大小超过了页的大小16KB，MySQL 会将该行的部分数据存储在行溢出页中。这意味着数据行会被分割，一部分存储在索引页中，而溢出的部分存储在单独的溢出页中），节点数的增加，导致树深度增大查询IO次数增加
    在这里插入图片描述

  • 第二点说明：“%小米 NFC 手机%” 查询中用做匹配的方式去查询，会导致索引失效，这样导致全表扫描。

  • 第三点说明：“小米 NFC 手机%” 去掉做匹配，走索引的方式，则会只查询"小米 NFC 手机"开头的，这样就会导致结果不准确

ElascitSearch索引解决方案
  • 对product字段进行分词拆分，得到如下一个词项 与id的匹配关系如下

在这里插入图片描述

  • 索引系统通过扫描文章中的每一个词，对其创建索引，指明在文章中出现的次数和位置，当用户查询时，索引系统过就会根据事先建立的索引进行查找，并将查找的结果反馈给用户的检索方式，利用如上表可以快速完成全文检索
  • 在为属性（product）构建倒排索引后，此时，本类别中包含了所有文档中所有字段的一个 分词（term） 文档id对应关系的字典信息通过倒排索引，我们可以迅速找到符合添加的文档，例如“手机” 在文档 1，2，3 中。
  • 当我们进行Elasticsearch查询，为了能快速找到某个term在倒排表中的位置，ElasticSearch 将类型中所有的term进行排序，然后通过二分法查找term，时间复杂度能达到 logN的查找效率，就像通过字典查找一样，这就是Term Dictionary，整个是二级辅助索引
  • 同时参照 B-Tree通过减少磁盘寻道次数来提高查询性能，Elasticsearch也是采用同样的思路，直接通过内存查找term，将term Dictionary这个构建的Mapping存放在内存中。但是如果term太多，term dictionary也会很大，放内存不现实，于是有了Term Index，因此整个ElasticSearch的数据结构如下图

在这里插入图片描述

压缩算法

这篇关于Interview preparation--elasticSearch倒排索引原理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1087358。

相关文章

mysql索引四（组合索引）

mysql索引四（组合索引）

单列索引，即一个索引只包含单个列，一个表可以有多个单列索引，但这不是组合索引；组合索引，即一个索引包含多个列。 因为有事，下面内容全部转自：https://www.cnblogs.com/farmer-cabbage/p/5793589.html 为了形象地对比单列索引和组合索引，为表添加多个字段： 　　 CREATE TABLE mytable( ID INT NOT NULL, use
阅读更多...
mysql索引三（全文索引）

mysql索引三（全文索引）

前面分别介绍了mysql索引一（普通索引）、mysql索引二（唯一索引）。 本文学习mysql全文索引。 全文索引（也称全文检索）是目前搜索引擎使用的一种关键技术。它能够利用【分词技术】等多种算法智能分析出文本文字中关键词的频率和重要性，然后按照一定的算法规则智能地筛选出我们想要的搜索结果。 在MySql中，创建全文索引相对比较简单。例如：我们有一个文章表（article），其中有主键ID（
阅读更多...
mysql索引二（唯一索引）

mysql索引二（唯一索引）

前文中介绍了MySQL中普通索引用法，和没有索引的区别。mysql索引一（普通索引） 下面学习一下唯一索引。 创建唯一索引的目的不是为了提高访问速度，而只是为了避免数据出现重复。唯一索引可以有多个但索引列的值必须唯一，索引列的值允许有空值。如果能确定某个数据列将只包含彼此各不相同的值，在为这个数据列创建索引的时候就应该使用关键字UNIQUE，把它定义为一个唯一索引。 添加数据库唯一索引的几种
阅读更多...
mysql索引一（普通索引）

mysql索引一（普通索引）

mysql的索引分为两大类，聚簇索引、非聚簇索引。聚簇索引是按照数据存放的物理位置为顺序的，而非聚簇索引则不同。聚簇索引能够提高多行检索的速度、非聚簇索引则对单行检索的速度很快。         在这两大类的索引类型下，还可以降索引分为4个小类型：         1，普通索引：最基本的索引，没有任何限制，是我们经常使用到的索引。         2，唯一索引：与普通索引
阅读更多...
数据库原理与安全复习笔记（未完待续）

数据库原理与安全复习笔记（未完待续）

1 概念 产生与发展：人工管理阶段 → \to → 文件系统阶段 → \to → 数据库系统阶段。 数据库系统特点：数据的管理者（DBMS）；数据结构化；数据共享性高，冗余度低，易于扩充；数据独立性高。DBMS 对数据的控制功能：数据的安全性保护；数据的完整性检查；并发控制；数据库恢复。 数据库技术研究领域：数据库管理系统软件的研发；数据库设计；数据库理论。数据模型要素 数据结构：描述数据库
阅读更多...
MySQL数据库（四）：视图和索引

MySQL数据库（四）：视图和索引

在数据库管理中，视图和索引是两种关键工具，它们各自发挥独特的作用以优化数据查询和管理。视图通过简化复杂查询、提高数据安全性和提供数据抽象，帮助用户轻松访问数据。而索引则通过加速查询、确保数据唯一性以及优化排序和分组操作，显著提升数据库性能。理解和合理运用这两者，对数据库系统的高效运行至关重要。 目录 一、视图概念（面试） 二、视图的作用（面试） 三、视图的创建和使用 3.1
阅读更多...
计算机组成原理——RECORD

计算机组成原理——RECORD

第一章 概论 1.固件  将部分操作系统固化——即把软件永恒存于只读存储器中。 2.多级层次结构的计算机系统 3.冯*诺依曼计算机的特点 4.现代计算机的组成：CPU、I/O设备、主存储器（MM） 5.细化的计算机组成框图 6.指令操作的三个阶段：取指、分析、执行 第二章 计算机的发展 1.第一台由电子管组成的电子数字积分和计算机（ENIAC） 第三章 系统总线
阅读更多...
GaussDB关键技术原理：高性能（二）

GaussDB关键技术原理：高性能（二）

GaussDB关键技术原理：高性能（一）从数据库性能优化系统概述对GaussDB的高性能技术进行了解读，本篇将从查询处理综述方面继续分享GaussDB的高性能技术的精彩内容。 2 查询处理综述 内容概要：本章节介绍查询端到端处理的执行流程，首先让读者对查询在数据库内部如何执行有一个初步的认识，充分理解查询处理各阶段主要瓶颈点以及对应的解决方案，本章以GaussDB为例讲解查询执行的几个主要阶段
阅读更多...
【计算机组成原理】部分题目汇总

【计算机组成原理】部分题目汇总

计算机组成原理 部分题目汇总 一. 简答题 RISC和CICS 简要说明，比较异同 RISC（精简指令集）注重简单快速的指令执行，使用少量通用寄存器，固定长度指令，优化硬件性能，依赖软件（如编译器）来提升效率。 CISC（复杂指令集）包含多样复杂的指令，能一条指令完成多步操作，采用变长指令，减少指令数但可能增加执行时间，倾向于硬件直接支持复杂功能减轻软件负担。 两者均追求高性能，但RISC
阅读更多...
MySQL数据库锁的实现原理

MySQL数据库锁的实现原理

MySQL数据库的锁实现原理主要涉及到如何确保在多用户并发访问数据库时，保证数据的完整性和一致性。以下是MySQL数据库锁实现原理的详细解释： 锁的基本概念和目的 锁的概念：在数据库中，锁是用于管理对公共资源的并发控制的机制。当多个用户或事务试图同时访问或修改同一数据时，数据库系统通过加锁来确保数据的一致性和完整性。 锁的目的：解决多用户环境下保证数据库完整性和一致性的问题。在并发的情况下，会
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2