MySQL和Lucene索引对比分析

本文涉及的产品
云数据库 RDS MySQL,集群系列 2核4GB
推荐场景:
搭建个人博客
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
云数据库 RDS MySQL,高可用系列 2核4GB
简介:

MySQL和Lucene都可以对数据构建索引并通过索引查询数据,一个是关系型数据库,一个是构建搜索引擎(Solr、ElasticSearch)的核心类库。两者的索引(index)有什么区别呢?以前写过一篇《Solr与MySQL查询性能对比》,只是简单的对比了下查询性能,对于内部原理却没有解释,本文简单分析下两者的索引区别。

MySQL索引实现

在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。

MyISAM索引实现

MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图:

图1是一个MyISAM表的主索引(Primary key)示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中,主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复。B+Tree的所有叶子节点包含所有关键字且是按照升序排列的。

MyISAM表的索引和数据是分离的,索引保存在”表名.MYI”文件内,而数据保存在“表名.MYD”文件内。

MyISAM的索引方式也叫做“非聚集”的,之所以这么称呼是为了与InnoDB的聚集索引区分。

InnoDB索引实现

虽然InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同。

第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道,MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。而在InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引。

图2是InnoDB主索引(同时也是数据文件)的示意图,可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以没有),如果没有显式指定,则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节,类型为长整形。

第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说,InnoDB的所有辅助索引都引用主键作为data域。例如,图3为定义在Col3上的一个辅助索引:

这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。

了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助,例如知道了InnoDB的索引实现后,就很容易明白为什么不建议使用过长的字段作为主键,因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大。再例如,用非单调的字段作为主键在InnoDB中不是个好主意,因为InnoDB数据文件本身是一颗B+Tree,非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键则是一个很好的选择。

讲MySQL索引的实现的文章很多,以上也是参考了《MySQL索引背后的数据结构及算法原理》,现在来看看Lucene的索引原理。

Lucene索引实现

Lucene的索引不是B+Tree组织的,而是倒排索引,Lucene的倒排索引由Term index,Team Dictionary和Posting List组成。

有倒排索引(invertedindex)就有正排索引(forwardindex),正排索引就是文档(Document)和它的字段Fields正向对应的关系:

DocID

name

sex

age

1

jack

18

2

lucy

17

3

peter

17

倒排索引是字段Field和拥有这个Field的文档对应的关系:

Sex字段:

[1,3]

[2]

Age字段:

18

[1]

17

[2,3]

Jack,lucy或者17,18这些叫做term,而[1,3]就是posting list。Posting list就是一个int型的数组,存储了所有符合某个term的文档id。那么什么是Term index和Term dictionary?

如上,假设name字段有很多个term,比如:Carla,Sara,Elin,Ada,Patty,Kate,Selena

如果按照这样的顺序排列,找出某个特定的term一定很慢,因为term没有排序,需要全部过滤一遍才能找出特定的term。排序之后就变成了:Ada,Carla,Elin,Kate,Patty,Sara,Selena

这样就可以用二分查找的方式,比全遍历更快地找出目标的term。如何组织这些term的方式就是 Term dictionary,意思就是term的字典。有了Term dictionary之后,就可以用比较少的比较次数和磁盘读次数查找目标。但是磁盘的随机读操作仍然是非常昂贵的,所以尽量少的读磁盘,有必要把一些数据缓存到内存里。但是整个Term dictionary本身又太大了,无法完整地放到内存里。于是就有了Term index。Term index有点像一本字典的大的章节表。比如:

A开头的term ……………. Xxx页

C开头的term ……………. Xxx页

E开头的term ……………. Xxx页

如果所有的term都是英文字符的话,可能这个term index就真的是26个英文字符表构成的了。但是实际的情况是,term未必都是英文字符,term可以是任意的byte数组。而且26个英文字符也未必是每一个字符都有均等的term,比如x字符开头的term可能一个都没有,而s开头的term又特别多。实际的term index是一棵trie 树:

上图例子是一个包含 "A", "to", "tea", "ted", "ten", "i", "in", 和 "inn" 的trie树。这棵树不会包含所有的term,它包含的是term的一些前缀。通过term index可以快速地定位到term dictionary的某个offset,然后从这个位置再往后顺序查找。再加上一些压缩技术(想了解更多,搜索 Lucene Finite State Transducers),Term index的尺寸可以只有所有term的尺寸的几十分之一,使得用内存缓存整个term index变成可能。整体上来说就是这样的效果:

由Term index到Term Dictionary,再到Posting List,通过某个字段的关键字去查询结果的过程就比较清楚了,通过多个关键字的Posting List进行AND或者OR进行交集或者并集的查询也简单了。

对比MySQL的B+Tree索引原理,可以发现:

1)Lucene的Term index和Term Dictionary其实对应的就是MySQL的B+Tree的功能,为关键字key提供索引。Lucene的inverted index可以比MySQL的b-tree检索更快。

2)Term index在内存中是以FST(finite state transducers)的形式保存的,其特点是非常节省内存。所以Lucene搜索一个关键字key的速度是非常快的,而MySQL的B+Tree需要读磁盘比较。

3)Term dictionary在磁盘上是以分block的方式保存的,一个block内部利用公共前缀压缩,比如都是Ab开头的单词就可以把Ab省去。这样Term dictionary可以比B-tree更节约磁盘空间。

4)Lucene对不同的数据类型采用了不同的索引方式,上面分析是针对field为字符串的,比如针对int,有TrieIntField类型,针对经纬度,就可以用GeoHash编码。

5)在 Mysql中给两个字段独立建立的索引无法联合起来使用,必须对联合查询的场景建立复合索引,而Lucene可以任何AND或者OR组合使用索引进行检索。

 

参考:

《MySQL索引背后的数据结构及算法原理》: http://blog.codinglabs.org/articles/theory-of-mysql-index.html

http://stackoverflow.com/questions/4628571/solr-date-field-tdate-vs-date

http://lucene.apache.org/core/

 

 

作者: 阿凡卢
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。
http://www.cnblogs.com/luxiaoxun/p/5452502.html
相关实践学习
如何在云端创建MySQL数据库
开始实验后,系统会自动创建一台自建MySQL的 源数据库 ECS 实例和一台 目标数据库 RDS。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程,来了解阿里云能够为你的业务带来哪些帮助     相关的阿里云产品:云服务器ECS 云服务器 ECS(Elastic Compute Service)是一种弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
相关文章
|
8天前
|
存储 关系型数据库 MySQL
阿里面试:为什么要索引?什么是MySQL索引?底层结构是什么?
尼恩是一位资深架构师,他在自己的读者交流群中分享了关于MySQL索引的重要知识点。索引是帮助MySQL高效获取数据的数据结构,主要作用包括显著提升查询速度、降低磁盘I/O次数、优化排序与分组操作以及提升复杂查询的性能。MySQL支持多种索引类型,如主键索引、唯一索引、普通索引、全文索引和空间数据索引。索引的底层数据结构主要是B+树,它能够有效支持范围查询和顺序遍历,同时保持高效的插入、删除和查找性能。尼恩还强调了索引的优缺点,并提供了多个面试题及其解答,帮助读者在面试中脱颖而出。相关资料可在公众号【技术自由圈】获取。
|
22天前
|
SQL 关系型数据库 MySQL
案例剖析:MySQL唯一索引并发插入导致死锁!
案例剖析:MySQL唯一索引并发插入导致死锁!
案例剖析:MySQL唯一索引并发插入导致死锁!
|
16天前
|
存储 关系型数据库 MySQL
Mysql(4)—数据库索引
数据库索引是用于提高数据检索效率的数据结构,类似于书籍中的索引。它允许用户快速找到数据,而无需扫描整个表。MySQL中的索引可以显著提升查询速度,使数据库操作更加高效。索引的发展经历了从无索引、简单索引到B-树、哈希索引、位图索引、全文索引等多个阶段。
50 3
Mysql(4)—数据库索引
|
1天前
|
数据管理 大数据 OLAP
AnalyticDB核心概念详解:表、索引与分区
【10月更文挑战第25天】在大数据时代,高效的数据库管理和分析工具变得尤为重要。阿里云的AnalyticDB(ADB)是一款完全托管的实时数据仓库服务,能够支持PB级数据的实时查询和分析。作为一名数据工程师,我有幸在多个项目中使用过AnalyticDB,并积累了丰富的实践经验。本文将从我个人的角度出发,详细介绍AnalyticDB的核心概念,包括表结构设计、索引类型选择和分区策略,帮助读者更有效地组织和管理数据。
10 3
|
21天前
|
存储 缓存 关系型数据库
MySQL事务日志-Redo Log工作原理分析
事务的隔离性和原子性分别通过锁和事务日志实现,而持久性则依赖于事务日志中的`Redo Log`。在MySQL中,`Redo Log`确保已提交事务的数据能持久保存,即使系统崩溃也能通过重做日志恢复数据。其工作原理是记录数据在内存中的更改,待事务提交时写入磁盘。此外,`Redo Log`采用简单的物理日志格式和高效的顺序IO,确保快速提交。通过不同的落盘策略,可在性能和安全性之间做出权衡。
1585 14
|
8天前
|
存储 关系型数据库 MySQL
基于案例分析 MySQL 权限认证中的具体优先原则
【10月更文挑战第26天】本文通过具体案例分析了MySQL权限认证中的优先原则,包括全局权限、数据库级别权限和表级别权限的设置与优先级。全局权限优先于数据库级别权限,后者又优先于表级别权限。在权限冲突时,更严格的权限将被优先执行,确保数据库的安全性与资源合理分配。
|
9天前
|
存储 关系型数据库 MySQL
如何在MySQL中进行索引的创建和管理?
【10月更文挑战第16天】如何在MySQL中进行索引的创建和管理?
31 1
|
23天前
|
SQL 自然语言处理 关系型数据库
Vanna使用ollama分析本地MySQL数据库
这篇文章详细介绍了如何使用Vanna结合Ollama框架来分析本地MySQL数据库,实现自然语言查询功能,包括环境搭建和配置流程。
123 0
|
11天前
|
监控 关系型数据库 MySQL
mysql8索引优化
综上所述,深入理解和有效实施这些索引优化策略,是解锁MySQL 8.0数据库高性能查询的关键。
24 0
|
14天前
|
SQL 关系型数据库 MySQL
美团面试:mysql 索引失效?怎么解决? (重点知识,建议收藏,读10遍+)
本文详细解析了MySQL索引失效的多种场景及解决方法,包括破坏最左匹配原则、索引覆盖原则、前缀匹配原则、`ORDER BY`排序不当、`OR`关键字使用不当、索引列上有计算或函数、使用`NOT IN`和`NOT EXISTS`不当、列的比对等。通过实例演示和`EXPLAIN`命令分析,帮助读者深入理解索引失效的原因,并提供相应的优化建议。文章还推荐了《尼恩Java面试宝典》等资源,助力面试者提升技术水平,顺利通过面试。

热门文章

最新文章