Elasticsearch查询速度为什么这么快？
这段时间在维护产品的搜索功能 ， 每次在管理台看到 Elasticsearch 这么高效的查询效率我都很好奇他是如何做到的 。
文章插图
这甚至比在我本地使用 MySQL 通过主键的查询速度还快 。
文章插图
文章插图
为此我搜索了相关资料：
文章插图
这类问题网上很多答案 ， 大概意思呢如下：ES 是基于 Lucene 的全文检索引擎 ， 它会对数据进行分词后保存索引 ， 擅长管理大量的索引数据 ， 相对于 MySQL 来说不擅长经常更新数据及关联查询 。
说的不是很透彻 ， 没有解析相关的原理;不过既然反复提到了索引 ， 那我们就从索引的角度来对比下两者的差异 。
MySQL 索引先从 MySQL 说起 ， 索引这个词想必大家也是烂熟于心 ， 通常存在于一些查询的场景 ， 是典型的空间换时间的案例 。 以下内容以 InnoDB 引擎为例 。
常见的数据结构假设由我们自己来设计 MySQL 的索引 ， 大概会有哪些选择呢?
①散列表首先我们应当想到的是散列表 ， 这是一个非常常见且高效的查询、写入的数据结构 ， 对应到 Java 中就是 HashMap 。
文章插图
这个数据结构应该不需要过多介绍了 ， 它的写入效率很高 O(1) ， 比如我们要查询 id=3 的数据时 ， 需要将 3 进行哈希运算 ， 然后再这个数组中找到对应的位置即可 。
但如果我们想查询 1≤id≤6 这样的区间数据时 ， 散列表就不能很好的满足了 ， 由于它是无序的 ， 所以得将所有数据遍历一遍才能知道哪些数据属于这个区间 。
②有序数组
文章插图
有序数组的查询效率也很高 ， 当我们要查询 id=4 的数据时 ， 只需要通过二分查找也能高效定位到数据 O(logn) 。
同时由于数据也是有序的 ， 所以自然也能支持区间查询;这么看来有序数组适合用做索引咯?
自然是不行 ， 它有另一个重大问题;假设我们插入了 id=2.5 的数据 ， 就得同时将后续的所有数据都移动一位 ， 这个写入效率就会变得非常低 。
③平衡二叉树既然有序数组的写入效率不高 ， 那我们就来看看写入效率高的 ， 很容易就能想到二叉树 。
这里我们以平衡二叉树为例：
文章插图
由于平衡二叉树的特性：左节点小于父节点、右节点大于父节点 。
所以假设我们要查询 id=11 的数据 ， 只需要查询 10→12→11 便能最终找到数据 ， 时间复杂度为 O(logn) ， 同理写入数据时也为 O(logn) 。
但依然不能很好的支持区间范围查找 ， 假设我们要查询 5≤id≤20 的数据时 ， 需要先查询 10 节点的左子树再查询 10 节点的右子树最终才能查询到所有数据 。 导致这样的查询效率并不高 。
④跳表跳表可能不像上边提到的散列表、有序数组、二叉树那样日常见的比较多 ， 但其实 Redis 中的 sort set 就采用了跳表实现 。 这里我们简单介绍下跳表实现的数据结构有何优势 。
我们都知道即便是对一个有序链表进行查询效率也不高 ， 由于它不能使用数组下标进行二分查找 ， 所以时间复杂度是 o(n) 。
但我们也可以巧妙的优化链表来变相的实现二分查找 ， 如下图：
推荐阅读
- iQOO 7官方美图赏：三种配色、速度美学设计传承
- AI战疫、真5G来了，十大最热门科技应用演绎速度与温度
- 首款7GB/s SSD！三星980PRO 1TB评测：永恒的1.8GB/s缓外写入速度
- 小米11 PK 小米10：传输速度提升1.6倍
- 4G速度变慢？运营商这波操作，让5G秒变“真香现场”
- 专家介绍如何判断智能手机被入侵：运行速度变慢、电池消耗过快以及卡顿
- 马化腾这招太高明！网友：只要我改名的速度够快，禁令就追不上我
- 怎样提高苹果6的运行速度？有这些问题就别救了，你用了几年了？
- 用户|4G速度慢了！5G也难逃“真香定律”
- 健康宝，保健康不保隐私？