数据结构

引言 MySQL的InnoDB引擎使用B+树作为索引的数据结构。理解B+树是掌握索引优化的基础。 一、从二叉树到B+树的演进 1.1 二叉查找树（BST） 10 / \ 5 15 / \ / \ 3 7 12 20 问题：可能退化为链表，查询O(n) 1.2 平衡二叉树（AVL） 通过旋转保持平衡，查询O(log n)。 问题： 每个节点只存1个元素 树高度大：100万数据需要20层 磁盘IO次数多（每层一次IO） 1.3 B树 [10, 20, 30] / | | \ [1,5] [12,15] [22,25] [35,40] 特点： 多路：每个节点存多个元素 所有节点都存数据 降低树高度 问题： 非叶子节点也存数据，占用空间 范围查询需要中序遍历 1.4 B+树 非叶子节点（只存索引）： [10, 20, 30] / | | \ / | | \ 叶子节点（存数据+索引）： [1,5,8] → [10,12,15] → [20,22,25] → [30,35,40] ↑ 双向链表 ↑ 特点： ...

引言 “计算机科学领域的任何问题都可以通过增加一个间接的中间层来解决。” —— David Wheeler 在上一篇文章《MySQL第一性原理:为什么我们需要数据库?》中,我们了解到MySQL通过索引将查询性能从O(n)提升到O(log n),实现了10万倍的性能飞跃。 但你有没有想过: 为什么索引能这么快? 从1亿条数据中查找一条,只需要3-4次磁盘IO 为什么MySQL选择B+树? 而不是哈希表、二叉搜索树、红黑树? 为什么有些查询用不上索引? WHERE id + 1 = 100 vs WHERE id = 99 联合索引的最左前缀原则是什么? 为什么(user_id, created_time)索引无法优化WHERE created_time > xxx? 今天,我们从第一性原理出发,通过对比5种数据结构,深度剖析MySQL索引的演进历程: 顺序扫描 → 哈希索引 → 二叉搜索树 → B树 → B+树 O(n) O(1) O(log₂n) O(logₘn) O(logₘn) + 顺序IO 1秒 ? ? ? 10微秒 我们还将手写300行代码,实现一个简化版B+树,彻底理解索引的实现原理。 一、问题的起点:全表扫描的性能瓶颈 让我们从一个最简单的查询开始: -- 用户表,1亿条数据 SELECT * FROM users WHERE id = 50000000; 如果没有索引,MySQL会怎么做? 1.1 顺序扫描（Full Table Scan） 执行过程: 1. 从磁盘读取第1页数据（16KB,约100行）→ 判断id是否等于50000000 → 不是 2. 从磁盘读取第2页数据 → 判断 → 不是 3. 从磁盘读取第3页数据 → 判断 → 不是 ... 500000. 从磁盘读取第50万页数据 → 判断 → 是! ✅ 总计:扫描50万页,约8GB数据 性能分析: ...

引言 “计算机科学领域的任何问题都可以通过增加一个间接的中间层来解决。” —— David Wheeler 在上一篇文章《MySQL第一性原理:为什么我们需要数据库?》中,我们了解到MySQL通过索引将查询性能从O(n)提升到O(log n),实现了10万倍的性能飞跃。 但你有没有想过: 为什么索引能这么快? 从1亿条数据中查找一条,只需要3-4次磁盘IO 为什么MySQL选择B+树? 而不是哈希表、二叉搜索树、红黑树? 为什么有些查询用不上索引? WHERE id + 1 = 100 vs WHERE id = 99 联合索引的最左前缀原则是什么? 为什么(user_id, created_time)索引无法优化WHERE created_time > xxx? 今天,我们从第一性原理出发,通过对比5种数据结构,深度剖析MySQL索引的演进历程: 顺序扫描 → 哈希索引 → 二叉搜索树 → B树 → B+树 O(n) O(1) O(log₂n) O(logₘn) O(logₘn) + 顺序IO 1秒 ? ? ? 10微秒 我们还将手写300行代码,实现一个简化版B+树,彻底理解索引的实现原理。 一、问题的起点:全表扫描的性能瓶颈 让我们从一个最简单的查询开始: -- 用户表,1亿条数据 SELECT * FROM users WHERE id = 50000000; 如果没有索引,MySQL会怎么做? 1.1 顺序扫描（Full Table Scan） 执行过程: 1. 从磁盘读取第1页数据（16KB,约100行）→ 判断id是否等于50000000 → 不是 2. 从磁盘读取第2页数据 → 判断 → 不是 3. 从磁盘读取第3页数据 → 判断 → 不是 ... 500000. 从磁盘读取第50万页数据 → 判断 → 是! ✅ 总计:扫描50万页,约8GB数据 性能分析: ...

一、引子：为什么Redis需要五大数据结构？ 很多人的疑问：Memcached只有String一种数据结构，Redis为什么需要五种？ 核心答案：不同的业务场景需要不同的数据结构。 1.1 如果只有String会怎样？ 假设我们要实现一个排行榜功能，只有String的话： // ❌ 方案1：用String存储整个排行榜（JSON序列化） // 问题：每次更新一个用户分数，需要序列化/反序列化整个排行榜 public void updateScore(Long userId, int score) { // 1. 读取整个排行榜（反序列化） String json = redisTemplate.opsForValue().get("rank:list"); List<User> rankList = JSON.parseArray(json, User.class); // 10000个用户 // 2. 更新一个用户的分数 for (User user : rankList) { if (user.getId().equals(userId)) { user.setScore(score); break; } } // 3. 重新排序 rankList.sort((a, b) -> b.getScore() - a.getScore()); // 4. 写入Redis（序列化） String newJson = JSON.toJSONString(rankList); redisTemplate.opsForValue().set("rank:list", newJson); } // 性能问题： // - 读取：反序列化10000个用户，耗时100ms // - 排序：O(NlogN) = 10000*log(10000) ≈ 130000次比较 // - 写入：序列化10000个用户，耗时100ms // 总耗时：200ms+（单次更新） // ✅ 方案2：使用Redis ZSet（有序集合） // 优势：Redis内部维护排序，O(logN)复杂度 public void updateScore(Long userId, int score) { redisTemplate.opsForZSet().add("rank:zset", userId.toString(), score); } // 性能提升： // - 写入：O(logN) = log(10000) ≈ 13次比较 // - 总耗时：1ms // 性能提升：200倍 核心洞察： ...

一、引子：为什么Redis需要五大数据结构？ 很多人的疑问：Memcached只有String一种数据结构，Redis为什么需要五种？ 核心答案：不同的业务场景需要不同的数据结构。 1.1 如果只有String会怎样？ 假设我们要实现一个排行榜功能，只有String的话： // ❌ 方案1：用String存储整个排行榜（JSON序列化） // 问题：每次更新一个用户分数，需要序列化/反序列化整个排行榜 public void updateScore(Long userId, int score) { // 1. 读取整个排行榜（反序列化） String json = redisTemplate.opsForValue().get("rank:list"); List<User> rankList = JSON.parseArray(json, User.class); // 10000个用户 // 2. 更新一个用户的分数 for (User user : rankList) { if (user.getId().equals(userId)) { user.setScore(score); break; } } // 3. 重新排序 rankList.sort((a, b) -> b.getScore() - a.getScore()); // 4. 写入Redis（序列化） String newJson = JSON.toJSONString(rankList); redisTemplate.opsForValue().set("rank:list", newJson); } // 性能问题： // - 读取：反序列化10000个用户，耗时100ms // - 排序：O(NlogN) = 10000*log(10000) ≈ 130000次比较 // - 写入：序列化10000个用户，耗时100ms // 总耗时：200ms+（单次更新） // ✅ 方案2：使用Redis ZSet（有序集合） // 优势：Redis内部维护排序，O(logN)复杂度 public void updateScore(Long userId, int score) { redisTemplate.opsForZSet().add("rank:zset", userId.toString(), score); } // 性能提升： // - 写入：O(logN) = log(10000) ≈ 13次比较 // - 总耗时：1ms // 性能提升：200倍 核心洞察： ...

引言 你是否好奇：为什么Redis的有序集合（ZSet）能在O(logN)时间内完成插入、删除、查找和范围查询？为什么Redis选择跳表（SkipList）而不是更常见的红黑树或AVL树？ 今天我们深入剖析跳表的设计思想和实现细节，理解这个优雅而高效的数据结构。 一、从问题出发：有序集合的需求 1.1 ZSet的典型操作 # 添加元素（带分数） 127.0.0.1:6379> ZADD ranking 95 "张三" 88 "李四" 92 "王五" (integer) 3 # 按分数范围查询 127.0.0.1:6379> ZRANGEBYSCORE ranking 90 100 1) "王五" # 92分 2) "张三" # 95分 # 查询排名 127.0.0.1:6379> ZRANK ranking "李四" (integer) 0 # 第0名（分数最低） # 删除元素 127.0.0.1:6379> ZREM ranking "李四" (integer) 1 1.2 性能需求 操作 时间复杂度要求 插入元素 O(logN) 删除元素 O(logN) 查找元素 O(logN) 范围查询 O(logN + M)，M为结果数量 获取排名 O(logN) 1.3 候选数据结构 数据结构 插入/删除/查找 范围查询 实现复杂度 内存占用 有序数组 O(N) O(logN + M) 简单 低 平衡二叉树（AVL/红黑树） O(logN) O(logN + M) 复杂 中 B树/B+树 O(logN) O(logN + M) 复杂 中 跳表（SkipList） O(logN) O(logN + M) 简单 中 Redis选择跳表的理由： ...

引言 在Redis中，我们使用SET和GET命令操作字符串，看起来和C语言的字符串没什么区别。但实际上，Redis并没有使用C语言传统的字符串表示（以空字符’\0’结尾的字符数组），而是自己实现了一种名为SDS（Simple Dynamic String，简单动态字符串）的抽象类型。 为什么要重新实现字符串？SDS有什么优势？今天我们深入源码，揭开SDS的神秘面纱。 一、C字符串的局限性 1.1 C字符串的表示 // C语言字符串 char str[] = "Redis"; // 内存布局 +---+---+---+---+---+---+ | R | e | d | i | s | \0| +---+---+---+---+---+---+ 0 1 2 3 4 5 1.2 存在的问题 问题1：获取字符串长度O(n) // 需要遍历整个字符串直到遇到'\0' size_t len = strlen(str); // O(n) 时间复杂度 // 对于频繁获取长度的场景（如Redis命令），性能损失严重 问题2：不支持二进制数据 // C字符串以'\0'作为结尾标志 char binary_data[] = {0x01, 0x02, 0x00, 0x03}; // ❌ 无法正确处理 // strlen会在遇到0x00时停止，认为字符串结束 // 导致无法存储图片、音频等二进制数据 问题3：容易缓冲区溢出 char dest[5] = "Hi"; char src[] = "Redis"; // ❌ 危险操作：没有检查dest空间是否足够 strcat(dest, src); // 缓冲区溢出！破坏相邻内存 问题4：内存重分配频繁 // 字符串拼接需要重新分配内存 char *str = malloc(6); strcpy(str, "Redis"); // 追加内容，需要重新分配 str = realloc(str, 12); // 每次都要重新分配，性能差 strcat(str, " Fast"); 问题5：不兼容部分C函数 // 很多C函数假设字符串以'\0'结尾 // 对于包含'\0'的二进制数据，这些函数无法正常工作 1.3 Redis的需求 Redis作为高性能数据库，对字符串的需求： ...

引言 上一篇我们学习了String类型，可以用JSON序列化存储对象。但是有一个问题： 如果只想修改用户的一个字段（比如年龄），需要怎么做？ // String方式：读取→反序列化→修改→序列化→写入 String json = redis.get("user:1001"); User user = JSON.parseObject(json, User.class); user.setAge(26); // 只改了年龄 redis.set("user:1001", JSON.toJSONString(user)); 这样做有几个问题： ❌ 需要整个对象序列化/反序列化 ❌ 网络传输整个对象（浪费带宽） ❌ 并发修改容易出现覆盖问题 Hash类型就是为了解决这个问题而生的。 一、Hash的本质 1.1 什么是Hash？ Hash就是一个键值对集合（类似Java的HashMap、Python的dict）： Hash对象 ├── field1: value1 ├── field2: value2 └── field3: value3 在Redis中： 外层键（Key）：对象的唯一标识 内层字段（Field）：对象的属性名 值（Value）：属性值 示例： # 用户对象 user:1001 ├── name: "张三" ├── age: "25" ├── email: "zhangsan@example.com" └── city: "北京" 1.2 Hash vs String 维度 String (JSON) Hash 存储方式 整个对象序列化为JSON 每个字段单独存储 修改单个字段 需要整体读写 直接修改该字段 内存占用 略高（JSON格式化） 略低（原生存储） 可读性 好（JSON可读） 一般（需遍历） 性能 读写整个对象 按需读写字段 适用场景 整体读写 频繁修改部分字段 选择原则： ...

引言 在Redis的五大基础数据类型中，String是最基础、最常用的一种。据统计，在实际生产环境中，80%以上的Redis键都是String类型。 但String远不止"字符串"这么简单。它可以： 存储任意二进制数据（文本、数字、图片、序列化对象） 作为计数器（原子性递增/递减） 实现分布式锁 存储位图数据 今天我们从第一性原理出发，理解String的本质和强大之处。 一、String的本质 1.1 不只是字符串 在Redis中，String类型的"String"是一个容易误导人的名字。它实际上是： 二进制安全的字节数组（Binary Safe Byte Array） 这意味着： ✅ 可以存储文本：“hello world” ✅ 可以存储数字：123456 ✅ 可以存储JSON：{"name":"Redis"} ✅ 可以存储序列化对象：Java对象、Protobuf ✅ 可以存储二进制数据：图片、音频（理论上，但不推荐） 1.2 底层实现：SDS Redis使用自己实现的简单动态字符串（Simple Dynamic String, SDS），而不是C语言原生的字符串。 C字符串的问题： char* str = "hello"; // 问题1：获取长度需要遍历，O(n) int len = strlen(str); // 问题2：不是二进制安全，遇到\0就截断 char* binary = "hello\0world"; // 只能读到"hello" // 问题3：缓冲区溢出风险 strcat(str, " world"); // 可能溢出 SDS的优势： struct sdshdr { int len; // 已使用长度 int free; // 剩余可用空间 char buf[]; // 实际存储的字节数组 }; 优势： O(1)时间获取长度：直接读取len字段 二进制安全：不依赖\0判断结束 预分配空间：减少内存分配次数 惰性释放：空间不立即释放，可重用 1.3 内存占用 一个简单的String在Redis中的内存占用： ...