Data Structures & Algorithms

1. 堆是什么 逻辑上看成一棵树，实际上是个数组。 - 位置关系 在数组起始位置为0的情形中： - 父节点i的左子节点在位置 2 i + 1 - 父节点i的右子节点在位置 2 i + 2 - 子节点i的父节点在位置 (i - 1) / 2 - 排序属性 - 最大堆：父节点的值 左右节点 - 最小堆：

1. BitMap是什么 - 又叫位图 - 把数据存放在一个以bit为单位的数据结构里，每位都只有0和1两个值。为0的时候，证明值不存在；为1的时候说明存在。 1.1. 举例 这个时候假如我们要存放2 4 6 8 9 10 17 19 21这些数字到我们的BitMap里，我们只需把对应的位设置为1就

1. 为什么需要BloomFilter 1.1. BloomFiler vs HashSet 一个网站有 20 亿 url 存在一个黑名单中，这个黑名单要怎么存？ 若此时随便输入一个 url，你如何快速判断该 url 是否在这个黑名单中？并且需在给定内存空间（比如：500M）内快速判断出 - 如果使

1. 图是什么 - 由边和顶点组成 2. 图分类 有方向 无方向 ------ --------- --------- 有权重 有向有权图 无向有权图 无权重 有向无权图 无向无权图 3. 图的表示 3.1. 邻接矩阵 - 用二维数组存储顶点之间的关系：两顶点相邻则为1，不相邻则为 0 - 3.2.

1. 是什么 - 一种树结构，区别在于是孩子指向父亲 2. 有什么用 - 解决连接问题（比路径问题更加简单） 3. 实现 3.1. API 3.2. Quick Find 3.2.1. 测试 3.3. Quick Union - 3.3.1. 测试 3.4. 基于size的优化 3.4.1. 测试

1. 是什么 - log-structured merge-tree - 一种数据结构，用于write-heavy的场景 2. 为什么LSM适合写多读少 - 利用了磁盘顺序写的速度快于磁盘随机写 3. 数据结构 3.1. SSTables - Sorted Strings Table - 数据持久化

1. 什么是ziplist - Redis底层的一种数据结构，用于实现list、zset > 2026 注：这是旧版 Redis 的实现背景；现代 Redis 已不再以 ziplist 作为这些结构的主要编码。 - 一段连续的内存空间 2. 为什么需要ziplist - 动态数组：由长度+元素列表组成。每个元素占用的空间大小相同，类型也是相同的 - - ziplist：也由长度+元素列表组成。不同之处在于 - 每个元素

1. B Tree是什么 - self-balance search tree中的一种 - 是个多叉查找树 - 2. 为什么需要B Tree 2.1. 背景 - 数据库查询的需求： - 根据某个值查找数据，比如 select from user where id=1234； - 根据区间值来查找某些

1. 什么是稀疏索引 - 首先他是个索引 - 索引.md - 其次他是稀疏的 - 稀疏索引和密集索引的区别在于是否为每个key都建立索引 2. 为什么需要稀疏索引 稀疏索引占用空间小 2.1. 稀疏索引 vs 密集索引 稀疏索引 密集索引 ------------------ -----------

1. 索引是什么 - 索引是一种把查找关键字和对应的数据记录关联起来（可以看作key-value对）的数据结构 - 索引查找是通过索引来查找数据 2. 为什么需要索引 - 用来加速数据的查找 3. 稀疏索引 vs 稠密索引 - 稀疏索引.md 4. 正排索引 vs 倒排索引 - 倒排索引.md 5.