学做网站在什么地方学,品牌公司设计,怎样做安居客网站,做网站用什么服务器比较好搜索引擎应该具备哪些要求
查询速度快 优秀的索引结构设计高效率的压缩算法快速的编码和解码速度 结果准确 ElasiticSearch 中7.0 版本之后默认使用BM25 评分算法ElasticSearch 中 7.0 版本之前使用 TP-IDF算法
倒排索引原理
当我们有如下列表数据信息#xff0c;并且系统…搜索引擎应该具备哪些要求
查询速度快 优秀的索引结构设计高效率的压缩算法快速的编码和解码速度 结果准确 ElasiticSearch 中7.0 版本之后默认使用BM25 评分算法ElasticSearch 中 7.0 版本之前使用 TP-IDF算法
倒排索引原理
当我们有如下列表数据信息并且系统数据量达到10亿100亿级别的时候我们系统该如何去解决查询速度的问题。数据库选择—mysql sybaseoraclemongodb唯一加速查询的方法是添加索引
索引
无论哪一种存储引擎的索引都是如下几个特点 帮助快速检索以数据结构为载体以文件的形式落地 如下图中mysql的文件形式其中的idb文件就是使用innodb存储引擎来实现数据存储生成的文件其他后缀的文件是其他存储引擎生成的因此无论什么引擎索引方式数据结构最终都是要落文件的 传统数据库的基本结构如下 MySql包括Server层和存储引擎层Server层包括连接器查询缓存分析器优化器执行器连接器负责和客户端建立连接查询缓存MySql获取到查询请求后会先查询缓存如果之前已经执行过一样的语句结果会以Key-value的形式存储到内存中key是查询语句value是查询结果。缓存明中的话可以很快完成查询但是大多是情况不能明中不建议用缓存因为缓存失效非常频繁任何对表的更新都会让缓存晴空所以对一个进程更改的表而言查询缓存基本不可用除非是一张配置表。可以通过配置来决定释放开启查询缓存并且MySql8.0 之间删除了查询缓存功能分析器词法分析识别语句中表名列名语法分析判断Sql是否满足MySql语法优化器在有多个索引的情况下决定使用哪个索引或者多表联合查询的时候表的连接顺序这么执行等执行器执行器先判断权限有权限才会去调用存储引擎对应的查询接口默认InnoDB
数据载体 mongodb mysql
以为mongodb为案例索引数据存储的结构如下 Mongodb索引使用的是B树B树是多叉平衡查找树包括以下几个结构特性 左子树数据小于跟数据右子树数据大于根节点数据左右子树高度差不大于1每个节点可以有N个字节的N2 B树的每个节点都存放 索引 数据数据遍布整个树结构搜索可能在非叶子结点结束最好情况是O(1) B树存在的问题 紫色部分存储数据的主键信息蓝色存储的是指针指向下一个节点黄色部分是存储的主键对应的数据Data。因此Data是在节点中占比最大的一部分数据他可能有1M或者更大的一个数据体假设我们一个节点的大小是固定的M在Mysql中最小的数据逻辑单元是数据页一个数据页是16KB如果Data越大M所能容纳的Data个数就越小如果需要存储更多的数据则需要更多的节点B树为了承载更多的节点的同时满足结构特性就需要更多的分叉因此就导致树的深度更大每一个层级都意味着一次IO操作导致IO次数更多 以为Mysql为案例分析 Mysql中innoDB 使用的索引结构是B树B 树是B树的变种区别在于 叶子结点保存了完整的索引 数据非叶子结点只保存索引值因此他的查询时间固定为logn叶子结点中有指向下一个叶子结点的指针叶子结点类似一个双向链表因为叶子结点有完整数据并且有双链表结构因此我们在范围查询的时候能有效提升查询效率。 数据都在子节点上因此非叶子节点就能容纳更多的索引信息这样就增加了同一个节点的出度减少了数据Data信息同一个节点就能容纳更多的其他类型数据信息因此能用更少的节点来承载索引数据节点的减少导致树的深度更低查询的IO次数就变少了。
倒排索引数据结构
对如上两个索引结构的分析我们能看到MySql 无法解决大数据索引问题 第一点索引往往字段很长如果使用Btrees树可能很深IO很可怕第二点索引可能会失效第三点查询准确度差 有如下案例有1亿条数据的商品信息我们需要对其中的product字段进行查询而且是文本信息查询例如“小米”这个字段查询那么有如下查询语句
select * from product where brand like %小米 NFC 手机%第一点说明以上查询语句我们需要在product上建索引 MySql上使用的B树因为文本的信息量特别的大导致所需要的节点就更多N个16KBMySql索引中如果一个数据行的大小超过了页的大小16KBMySQL 会将该行的部分数据存储在行溢出页中。这意味着数据行会被分割一部分存储在索引页中而溢出的部分存储在单独的溢出页中节点数的增加导致树深度增大查询IO次数增加 第二点说明“%小米 NFC 手机%” 查询中用了左匹配的方式去查询会导致索引失效这样导致全表扫描。 第三点说明“小米 NFC 手机%” 去掉左匹配走索引的方式则会只查询小米 NFC 手机开头的这样就会导致结果不准确
ElascitSearch索引解决方案
对product字段进行分词拆分得到如下一个词项 与id的匹配关系如下 Posting List 倒排表
索引系统通过扫描文章中的每一个词对其创建索引指明在文章中出现的次数和位置当用户查询时索引系统过就会根据事先建立的索引进行查找并将查找的结果反馈给用户的检索方式利用如上表可以快速完成全文检索在为属性product构建倒排索引后此时本类别中包含了所有文档中所有字段的一个 分词term 文档id对应关系的字典信息通过倒排索引我们可以迅速找到符合条件的文档例如“手机” 在文档 123 中。
Term Dictionary前缀树
当我们进行Elasticsearch查询为了能快速找到某个term在倒排表中的位置ElasticSearch 将类型中所有的term进行排序然后通过二分法查找term时间复杂度能达到 logN的查找效率就像通过字典查找一样这就是Term Dictionary整个是二级辅助索引
Term Index前缀索引
同时参照 B-Tree通过减少磁盘寻道次数来提高查询性能Elasticsearch也是采用同样的思路直接通过内存查找term将term Dictionary这个构建的Mapping存放在内存中。但是如果term太多term dictionary也会很大放内存不现实于是有了Term Index因此整个ElasticSearch的数据结构如下图 压缩算法
倒排表生成后可能存在如表中小米关键字匹配到的文档id有 100W个 int类型的有序数组如果直接存储这个数据的那么需要4Byte * 100w 4MB 的存储空间因此存储的时候需要用到一定的压缩算法来进行数据压缩
FOR Frame Of Reference压缩算法
假设我们获取到的压缩表数组id是[1,2,3,4,5,…100W] 每一个数据占用的存储空间是 4Byte 总共是100W * 4Byte 100W * 4 * 8 bit通过计算相邻数据差值 得到数组2 [1,1,1,1,1,1, ,1]总共有100W个1 这样我们可以将每一个数据用一个bit 来存储这样就只需要 100W * 1bit 相比于原来 数据 缩小了 32 倍如下图 当然以上是一个特殊的案例我们用一个相对正常一点的数组来重新计算 原数组[73,300,302,332,343,372] 总共 6*4Byte 24Byte 差值数组[732272301129]。我们得到如下结论。 64 73 128, 128 227 256, 124, 16 3032, 81116, 16 29 32, 以上数据我们就依然用bit位的存储方式我们用以上数组中最大的数字所需要的bit位来计算也就是227 用256 来存储 2 8 , 也就是8个bit位每个数字得到如下 [732272301129]。需要的存储。6 * 8bit 48bit 但是我们发现还是可以有优化空间比如 2 其实只需要一个bit位即可因此我们将大数小数再次做一次分组 [73, 227] 最大28 es中会做一个记录记录此处数组占用的是8bit。, [2, 30,11,29] 最大25 同样es中做记录此处占用5bit进一步缩小存储空间。 计算整个的存储空间 [73, 227] 部分。 8bit - 给es记录存储空间大小是8bit。数字占用 8bit * 2 总共。 8bit * 3 3Byte[2, 30,11,29] 部分。 8bit - 给es记录存储空间大小是5bit 数字占用 5bit * 4 总共。8 bit 20bit 4Byte因此总共也就7 Byte的空间占用 如下图 RBM压缩Roaring bitmaps 有了FOR算法而且针对于同一种数据结构为什么还需要RBM算法因为以上数据中案例数组都是比较稠密的数组也就是他们的差值都是比较小的值如果有如下数组 [1000W, 2000W, 3000W, 4000W, 5000W] 每个数都上千万差值也是千万级别这样用FOR算法就没有任何意义了。 RBM 案例讲解有如下案例[1000, 62101, 131385, 132052, 191173, 196658] 第一步我们将数字用二进制表示 例如。196658 转二进制是 0000 0000 0000 0011 0000 0000 0011 0010 第二步将二进制分为高16 位 0000 0000 0000 0011 转十进制是 2底16位 0000 0000 0011 0010 转十进制是50 通过以上步骤我们得到196658 的表示方式2 50 也可以通过计算方式得到这两个数字 196658 / 216 得到的值是2 余数是 50 这种计算方式得到我们的推测结果,并且得到的所有数字都小于 2 16 65536 我们将以上数组表示为 [(0,1000), (0,62101), (2,313), (2,980), (2,60101), (2,50)] 第三步用一个container的数据结构来存储以上得到的数据表 short[] 数组存储 第一个数字Arraybitmaprun 存储第二个数字的组合01000. 621012313980 6010150。。。。。。。。
我们将数字以第一个数字为基准做group by 聚合得到一个表RBM的存储方式有三种 ArrayContainerBitMapContainerRunContainer 三种 ArrayContainer存储short 类型的数组short类型最大是216 正好可以存储下所有数据的极限而第一个位置中的数字最大也就是65535因为我们通过X/65535 X最大也就是232 因此最多也就是。65535个行同样一个Array最多也是存储65536个id计算总存储占用short 2Byte 16bit 总共有65536个。65536* 2Byte / 1024 128KB因此一个行的数据最多存储128KB BitMapContainer存储位图存储的数据必须是不一样的数据因为避免冲突bitmap每一位不为0 的位都代表当前位的数据存在比如第10位 1表示数组中存在1 因此如果有数组[1,2,3,4,5,6,7], bitMap对应的就是7个bit位 如果65536 个数字都是不一样的那么用一个 65536 个bit位置的bitMap存储即可总共 65536 bit / 8 / 1024 8KB缺点是必须每个数字不一样 RunContainer存储按照如上思路如果存在如下特殊的数组[1,2,3,4,5,…100W] 那么可以表示为1 100W压缩到极致比例取决于连续数字的多少安以上三种算法有如下图表示 Term Dictionary Term Index
构建好倒排表之后就又能力快速找到某个term对于的文档id然后通过id查找磁盘上的segment新的问题产生了加入又1亿数据那么term可能又上百万挨个便利就炸了ElasticSearch为了快速找到对应term讲term按数组排序排序后二分查找以logN的查询时间复杂度完成查询这样就构建了一个类似如下的term Dictionary
[aaa, aba, abb,abc, allen, .... ,sara,sarb,sarc,....selena.....]即使是logN的时间复杂的在存在磁盘操作的情况 大数据量情况也是非常慢的如果讲term dictionary加载到内存十万级别的数据量可能就把内存沾满了因此需要另外一个更晓的数据来对term dictionary进行替代到内存中进行查询他就是 term index构建term index 过程 便利所有 term dictionary 中的数据按字符拆分构建成b-tree例如aaa 构建成 a-a-a其他分支依然按字符拆分如下图 以上前缀表中不会包含所有的term信息它包含的是term的前缀信息例如 aaaaabaac 都存在aa前缀通过term index可以快速地定位到term dictionary的某个offset再结合FST(Finite State Transducers)的压缩技术可以使term index缓存到内存中。从term index查到对应的term dictionary的block位置之后再去磁盘上找term大大减少了磁盘随机读的次数。如下图 FST 压缩算法
假设我们要将mop, moth, pop, star, stop and top(term index里的term前缀)映射到序号012345(term dictionary的block位置)。最简单的做法就是定义个Mapstring, integer“”大家找到自己的位置对应入座就好了但从内存占用少的角度看可以用FST来进行压缩后在存储到内存。如下图 O表示一种状态–表示状态的变化过程上面的字母/数字表示状态变化和权重将单词分成单个字母通过⭕️和–表示出来0权重不显示。如果⭕️后面出现分支就标记权重最后整条路径上的权重加起来就是这个单词对应的序号。FST以字节的方式存储所有的term这种压缩方式可以有效的缩减存储空间使得term index足以放进内存但这种方式也会导致查找时需要更多的CPU资源。
