数据结构

B树与LSM树:现代数据库存储引擎的核心数据结构

B+树与LSM树是存储引擎的两种核心本文从磁盘I/O模型出发,深入分析B+树的节点结构、分裂合并机制与范围查询优化,以及LSM树的MemTable、SSTable、多级Compaction策略与读写放大权衡,并结合MySQL InnoDB和RocksDB讲解工程实践

哈希表深度实战:从散列函数、拉链/开放寻址到 Robin Hood、完美哈希与并发哈希映射的工程全解

哈希表(Hash Table,又称散列表)是计算机科学里把「均摊 O(1) 查找」从理论变成工业现实的基石:字典、缓存、索引、去重、集合、计数、符号表,底层几乎都是它。本系列已覆盖布隆过滤器、Count-Min Sketch、HyperLogLog、Cuckoo 哈希等「概率/高性能」变体,却独缺最通用的那一枚——标准哈希表本身。本文从散列函数的第一性原理讲起,拆解拉链法与开放寻址的本质差异、负载…

后缀数组(Suffix Array)深度实战:从前缀倍增、SA-IS 到 LCP 数组与模式匹配的工程全解

后缀数组(Suffix Array,SA)是字符串处理领域最基础、最高效的索引结构之一。它把"一个字符串的所有后缀按字典序排序后的起始位置"紧凑地存成一个长度 n 的整数数组,却能在 O(m log n) 内完成任意模式串的精确匹配、在 O(n) 内求最长重复子串、不同子串计数、最长公共子串等经典问题。它比后缀树省内存、比后缀自动机易实现,是生物信息学(DNA 比对)、全文检索(FM-index …