面试真题分享-Redis中ZSET底层实现原理

可为编程

发布于 2024-07-08 12:29:55

930

发布于 2024-07-08 12:29:55

文章被收录于专栏：技术专栏全家桶

SQL深分页问题

应该就是limit 1000000 10这种类型的sql语句，遇到这种有以下几种方案：

在数据量⽐较⼤，分⻚⽐较深的情况下，需要考虑分⻚的优化。

例如：

select * from table where type = 2 and level = 9 order by id asc limit 190289,10;

优化⽅案：

延迟关联

先通过 where 条件提取出主键，在将该表与原数据表关联，通过主键 id 提取数据⾏，⽽不是通过原来的⼆级索引提取数据行。

例如：

select a.* from table a,
(select id from table where type = 2 and level = 9 order by id asc limit 190289,10 ) b
where a.id = b.id

书签⽅式

书签⽅式就是找到 limit 第⼀个参数对应的主键值，根据这个主键值再去过滤并 limit。

例如：

select * from table where id >
(select id from table where type = 2 and level = 9 order by id asc limit 190,1) limit 10;

以上两种方式并不高效，因为涉及到子查询，明显慢于一条sql语句。

ES原理机制与核心组件

以下是Elasticsearch的一些核心概念：

索引（Index）: 一个索引就是一个文档容器，它包含了很多文档，这些文档被存储并被分析过。相当于书的目录，所有关键字都建议创建成索引，然后根据索引查询数据，提高效率。这里的索引与数据库中索引不同，采用倒排索引。所谓的正向索引，就是搜索引擎会将待搜索的文件都对应一个文件 ID，搜索时将这个 ID 和搜索关键字进行对应，形成 K-V 对，然后对关键字进行统计计数，比如关系型数据库都是采用正向索引。倒排索引就是将关键字与ID数据相对应，每个关键词都对应着一系列的文档Doc，这些文档Doc中都出现这个关键词。倒排索引就是分词后将以前的索引与现在分词后的关键字相连。

keyword不可以分词，完整的查找

text可以分词

ik_max_word 最详细的分词，能拆都拆

ik_smart 最粗粒度的分词

词条：中文中一般是词组，索引中最小存储和查询单元

词典：字典，词条的集合，B+ HASH算法

倒排表：首先去搜索词典，看看我们查看的单词在不在词典中，如果不在结束，如果在就去看单词在这个列表中的指针，通过倒排列表去获取单词所对应的文档ID的列表，然后拿着文档ID再去找到对应的数据。先根据搜索的关键字找到对应的ID 再去找到具体的内容。

文档（Document）: 一个文档是一个可被索引的基本信息单元，例如一个客户的订单、一篇博客等，一条数据等都是一个文档数据。

类型（Type）: 在Elasticsearch中，一个索引可以定义一个或多个类型。类型是索引的逻辑类分割，通常是根据数据的不同来进行分割。

版本Type

5.x 支持多种 type

6.x 只能有一种 type

7.x 默认不再支持自定义索引类型（默认类型为：_doc）

节点（Node）: 一个Elasticsearch实例，可以是一个物理或虚拟的服务器。

集群（Cluster）: 由多个节点组成的网络，它们共享数据并提供搜索和服务功能。

分片（Shard）: 一个索引可以被分成多个分片，这些分片可以分布到不同的节点上。分片是ES实现数据水平扩展和高可用的关键。每个主分片有两个副本分片，副本数和节点数相关联。

副本（Replica）: 分片的副本，用于提供高可用性和提升搜索性能。每个主分片都有副本。

分词器（Analyzers）: 用于文本分析的组件，例如将文本分割成词的组件。ik分词器，keyword不可以分词，完整的查找。

text可以分词

ik_max_word 最详细的分词，能拆都拆

ik_smart 最粗粒度的分词

词条：中文中一般是词组，索引中最小存储和查询单元

词典：字典，词条的集合，B+ HASH算法

倒排表：首先去搜索词典，看看我们查看的单词在不在词典中，如果不在结束，如果在就去看单词在这个列表中的指针，通过倒排列表去获取单词所对应的文档ID的列表，然后拿着文档ID再去找到对应的数据。先根据搜索的关键字找到对应的ID 再去找到具体的内容。

线程之间的通信机制，如何通信的？

线程之间通信是多线程编程中一个重要的概念，它使得不同线程能够协同工作并共享信息。以下是一些常见的线程之间通信的机制：

1. 共享内存：

线程之间最常见的通信方式是通过共享内存。多个线程可以访问相同的内存区域，通过在这个共享内存中读写数据来进行通信。但要确保对共享数据的访问是线程安全的，通常需要使用同步机制，如锁。

2. 消息传递：

线程之间可以通过消息传递进行通信，即一个线程向另一个线程发送消息。这可以通过队列（Queue）实现，一个线程将消息放入队列，另一个线程从队列中取出消息进行处理。Java中的`BlockingQueue`阻塞队列是一个常用的实现方式。

3. 信号量（Semaphores）：

信号量是一种同步机制，它可以用于控制同时访问共享资源的线程数量。线程在访问共享资源之前必须获取信号量，而释放共享资源后需要释放信号量。信号量的值通常用于表示可以同时访问的线程数量。

4. 条件变量（Condition Variables）：

条件变量是一种同步工具，通常与锁结合使用。它允许线程在满足特定条件时等待，或者在条件发生变化时被唤醒。Java中的`ReentrantLock`和`Condition`接口提供了条件变量的实现。

5. 管道（Pipes）：

管道是一种进程间通信的方式，也可以在多线程环境中使用。在Java中，`PipedInputStream`和`PipedOutputStream`提供了管道的实现。

6. CountDownLatch和CyclicBarrier：

`CountDownLatch`和`CyclicBarrier`是Java中的两个同步工具，它们可以用于线程之间的协调。`CountDownLatch`用于等待一组线程完成，每个线程去执行，执行完将数量减1，然后下一个线程执行，最后将完成的结果返回处理，主线程需要每个线程的统计结果进行聚合，而`CyclicBarrier`用于等待一组线程互相达到屏障点之后再去统一执行，类似于王者荣耀的等待界面加载各个玩家。

7. Wait和Notify机制：

在Java中，通过`Object`类的`wait()`和`notify()`方法，以及`notifyAll()`方法，可以实现线程之间的等待和唤醒操作。这通常与`synchronized`关键字一起使用。

这些机制允许线程之间安全地共享信息，协同工作，以及避免竞态条件等问题。选择适当的通信机制取决于问题的性质和线程之间的关系。

MyBatis 的 xml 映射文件中，不同的 xml 映射文件的id 是否可以重复？

在 MyBatis 的 XML 映射文件中，不同的 XML 映射文件的 id 可以重复，但这个重复是有限制条件的：

如果配置了 namespace（命名空间）：那么，在不同 XML 映射文件中，即使 id 相同也是可以的，因为 MyBatis 在解析和使用时会结合每个映射文件的 namespace 与 id 来形成唯一的标识符。所以只要 namespace 不同，即使 id 相同也不会冲突。

如果没有配置 namespace：那么 id 是不能重复的，因为在没有 namespace 区分的情况下，相同的 id 会导致 MyBatis 解析时产生冲突，无法准确地定位到对应的 SQL 映射语句，进而影响程序的正常运行。

总结来说，在实际开发中，通常都会为每个 XML 映射文件定义唯一的 namespace，并且在内部的各个 SQL 映射元素上使用不重复的 id，以确保正确无误地执行 SQL 操作。namespace+id是作为Map<String,MappedStatement>的key使用的，因为map集合里面的key是不能重复的，那么namespace+id也是不能重复的。所以可以namespace相同id不同，或者namespace不同id相同，或者namespace不同id不同。

Mybatis的二级和一级缓存有什么用？

一级缓存默认开启，作用于SqlSession级别，各个SqlSession之间相互隔离互不影响。一级缓存基于 PerpetualCache 的 HashMap 本地缓存。同一个会话中当查询SQL执行多次的时候，会将查询结果存储到一级缓存中，然后直接从内存中查找到缓存中的数据，在同一个会话里面，多次执行相同的SQL语句，会直接从内存取到一级缓存的结果，不会再发送 SQL到数据库。但是不同的会话里面，即使执行的SQL一样(通过一个Mapper 的同一个方法的相同参数调用)，也不能使用到一级缓存。

一级缓存只能作用于查询会话中，所以也叫做会话缓存。

同一个会话中，update(包括 delete)会导致一级缓存被清空

问题:只有更新会清空缓存吗？查询会清空缓存吗？如果要清空呢？

一级缓存是在 BaseExecutor 中的 update()方法中调用 clearLocalCache()清空的(无条件)，如果是query会判断(只有select标签的 flushCache=true 才清空)

⼆级缓存与⼀级缓存其机制相同，默认也是采⽤ PerpetualCache，HashMap 存储，不同之处在于其存储作⽤域为 Mapper(Namespace)，可以在多个SqlSession之间共享，并且可⾃定义存储源，如 Ehcache。默认不打开⼆级缓存，要开启⼆级缓存需要进行配置，使⽤⼆级缓存属性类需要实现Serializable序列化接⼝(可⽤来保存对象的状态),可在它的映射⽂件中配置。

这两级缓存最大的区别就是：一级缓存是会话级别的，只要出了这个 SqlSession，缓存就没用了。而二级缓存可以跨会话（也就是多个Mapper的NameSpace），多个SqlSession会话可以使用相同的NameSpace缓存，一个NameSpace对应一个二级缓存。

二级缓存生效的条件

当会话事务提交或关闭之后才会填充二级缓存，因为事务TransactionalCacheManager中保存二级缓存的PerpetualCache 组件。
必须是同一个 mapper，即同一个命名空间namespace
必须是相同的 statement，即同一个 mapper 中的同一个方法
必须是相同的 SQL 语句和参数
如果 readWrite=true(默认就是true)，实体对像必须实现 Serializable 接口

缓存清除条件

只有修改会话提交之后，才会执行清空操作
xml 中配置的 update 不能清空 @CacheNamespace 中的缓存数据
任何一种增删改操作都会清空整个 namespace 中的缓存

Mapper.xml 配置了 <cache> 之后， select() 会被缓存。update() 、 delete() 、 insert() 会刷新缓存。

MYSQL为啥不用二叉树？

InnoDB和MyISAM都支持全文索引。

有序数组可以做索引，对于等值查询和和比较查询效率比较高，但是更新数据会移动大量数据，尾插法不用移动，所以适合存储静态数据。为了支持频繁的修改，比如插入数据，我们需要采用链表形式，但是单链表的查询效率比较低，如何能够使用二分查找算法的链表呢？为了解决这个问题BST （二叉查找树）诞生了。

二叉查找树的优缺点：

优点：

1、数据不多的情况下查询效率高

2、插入效率高，左节点小于根节点小于右节点

3、有序存储，从左到右依次递增

4、查询时间复杂度为O(LogN)

缺点：

1、二叉树的数据必须要有序，无序需要排序后才能组成二叉树结构进行查询和遍历

2、数据量大的情况下导致树特别高，从而查询检索比较耗时，最坏情况下退化成O(N)

3、当遇到一个有序的数组时会演化成单链表形式也就是最坏的情况。演化成单链表也叫做斜树

这种情况也会导致查询效率降低，因此需要找到一个可以保障平衡的树，树的深度相差不大的树，这个就是平衡二叉树，AVL树。但是AVL树又不能保障树的高，数据量一多就导致树很深，因此选择B+树更能兼顾这方面的性能，保障树高更均匀，也能够容纳更多的数据。

Redis中的zset在底层是通过什么数据结构来实现的？

ZSET主要由跳表和压缩表来实现，zset底层的存储结构包括ziplist或skiplist，在同时满足以下两个条件的时候使用ziplist，其他时候使用skiplist，两个条件如下：

有序集合保存的元素数量小于128个
有序集合保存的所有元素的长度小于64字节

当ziplist作为zset的底层存储结构时，每个集合元素使用两个紧挨在一起的压缩列表结点来保存，第一个结点保存元素的成员，第二个结点保存元素的分值，当skiplist作为zset的底层存储结构的时候，使用skiplist按序保存元素及分值，使用dict来保存元素和分值的映射关系。

ziplist数据结构

ziplist作为zset的存储结构时，格式如下图：

紧挨着的时元素member个分值score，整体数据是有序格式。

skiplist数据结构

skiplist作为zset的存储结构，整体存储结构如下图。核心点主要包括一个dict对象和一个skiplist对象。dict保存key/value，key为元素，value为分值；skiplist保存的有序的元素列表，每个元素包括元素和分值。两种数据结构下的元素指向相同的位置。

跳跃表（skiplist）是一种可以进行快速查找的有序数据结构，它通过维护多级索引来实现快速查找。这种方式的优点是查找和修改数据的性能较高，但是占用的内存也较多。当 zset 存储的元素数量较多，或者元素的字符串长度较长时，Redis 会选择使用跳跃表作为底层实现。

一个zset结构同时包含一个字典和一个跳跃表。跳跃表按score从小到大保存所有集合元素。而字典则保存着从member到score的映射，这样就可以用O(1)的复杂度来查找member对应的score值。虽然同时使用两种结构，但它们会通过指针来共享相同元素的member和score，因此不会浪费额外的内存。

zset的存储过程

zset的添加过程，以zadd的操作为例进行分析，整个过程如下：

解析参数得到每个元素及其对应的分值；
查找key对应的zset是否存在，不存在则创建；
如果存储格式是ziplist，那么在执行添加的过程中我们需要区分元素存在和不存在两种情况：
存在的情况下，先删除再添加；
不存在的情况下，添加，并且需要考虑元素的长度是否超出限制或实际已有的元素个数是否超过最大限制进而决定是否转为skiplist对象。
如果存储个数是skiplist，那么在执行添加的过程中我们需要区分元素存在和不存在两种情况：
存在的情况下线删除后添加；
不存在情况下那么久直接添加，在skiplist当中添加完以后我们同事需要更新dict对象。

当数据较少时：zset是由一个压缩链表来实现的

当数据较多时：zset是由一个字典+跳表来实现的。简单来讲，dict用来查询数据到分数的对应关系，而skiplist用来根据分数查询数据（可能是范围查找）

第1层链表不是一个单向链表，而是一个双向链表，这是为了方便以倒序方式获取一个范围内的元素。

MySQL 的 B+ 树和 Redis 的跳表都是用于存储有序数据的数据结构，但它们有一些关键的区别，使得它们在不同的场景和用途中各有优势。结构差异

B+ 树是一种多路搜索树，每个节点可以有多个子节点，而跳表是一种基于链表的数据结构，每个节点只有一个下一个节点，但可以有多个快速通道指向后面的节点。

空间利用率

B+ 树的磁盘读写操作是以页（MyISAM通常是 4KB,Innodb是16KB）为单位的，每个节点存储多个键值对，可以更好地利用磁盘空间，减少 I/O 操作。而跳表的空间利用率相对较低。

插入和删除操作

跳表的插入和删除操作相对简单，时间复杂度为 O(logN)，并且不需要像 B+ 树那样进行复杂的节点分裂和合并操作。

B+ 树的所有叶子节点形成了一个有序链表，因此非常适合进行范围查询。而跳表虽然也可以进行范围查询，但效率相对较低。

因此，B+ 树和跳表不能简单地相互替换。在需要大量进行磁盘 I/O 操作和范围查询的场景（如数据库索引）中，B+ 树可能是更好的选择。而在主要进行内存操作，且需要频繁进行插入和删除操作的场景（如 Redis）中，跳表可能更有优势。

Mysql 为什么使用 B +树，而不是跳表？