01 从一道经典算法题，看懂寻址的底层逻辑

（本文所有的「访问次数」，均指跨高延迟边界的动作 —— 比如一次RPC调用、一次对象存储GET/HEAD请求、一次磁盘读，这类有固定高开销的操作；CPU的纳秒级算术计算，不计入其中。我们的核心关注点只有一个：能不能减少I/O次数、把随机I/O变成顺序I/O。）

public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) return new int[]{i, j};
}
}
return null;
}

public int[] twoSum(int[] nums, int target) {
Map map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i]; // 核心：计算出需要找的值
if (map.containsKey(complement)) { // 核心：直接定位，无需遍历
return new int[]{map.get(complement), i};
}
map.put(nums[i], i);
}
return null;
}

02 HashMap：计算寻址的经典实现

2.1 HashMap的核心设计：Hash计算 + 数组直访

public class HashMap {
// 核心：数组，支持 O(1) 随机访问
transient Node[] table;
// 节点结构
static class Node {
final int hash;      // 哈希值（缓存，避免重复计算）
final K key;         // 键
V value;             // 值
Node next;      // 下一个节点（处理冲突）
}
// 哈希函数：key → 整数
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
}

2.2 HashMap的完整寻址过程（get/put通用）

1. 计算哈希值：通过hash函数把key转换成一个整数（比如 hash("apple")=93029210）；
2. 计算数组下标：通过 index = hash & (数组长度-1) 算出目标下标（比如 93029210 &15 =10）；
3. 精准定位bucket：直接访问数组的table[10]位置，这是一次内存随机访问；
4. 桶内精准命中：无冲突则直接读写，有冲突则在链表/红黑树做常数级比对。

2.3 为什么HashMap是O(1)？

element_address = base_address + index × element_size

• 链表查找：要遍历n个节点，触发n次内存访问，时间复杂度O(n)；
• 数组查找：计算地址，只触发1次内存访问，时间复杂度O(1)。

03 分布式存储的寻址升级

3.1 HDFS：大文件存储的寻址逻辑，核心是元数据全内存

// NameNode 内存中的数据结构
// 1. 文件系统目录树
class FSDirectory {
INodeDirectory rootDir;           // 根目录 "/"
INodeMap inodeMap;                // path → INode (HashMap!)
}
// 2. INode：文件/目录节点
abstract class INode {
long id;                          // 唯一标识
String name;                      // 名称
INode parent;                     // 父节点
long modificationTime;            // 修改时间
}
class INodeFile extends INode {
BlockInfo[] blocks;               // 文件包含的块列表
}
// 3. 块信息映射
class BlocksMap {
GSet blocks;    // Block → 位置信息 (HashMap!)
}
class BlockInfo {
long blockId;
DatanodeDescriptor[] storages;    // 存储这个块的 DataNode 列表
}

1. 客户端向NameNode发起1次RPC请求，获取文件的块位置信息；
2. NameNode在内存中完成路径解析+块映射查找（不触发磁盘IO），计算出200MB落在第2个块（默认块大小128MB）；
3. NameNode返回该块的存储节点列表（比如DN2、DN3）；
4. 客户端直连最近的DN2，直接读取该块数据。

3.2 Kafka：消息流存储的寻址逻辑，核心是稀疏索引+顺序存储

// Partition 管理所有 Segment
class LocalLog {
// 核心：TreeMap，按 baseOffset 排序
ConcurrentNavigableMap segments;
// 定位 Segment
LogSegment floorEntry(long offset) {
return segments.floorEntry(offset);  // O(log N)
}
}
// 单个 Segment
class LogSegment {
FileRecords log;           // .log 文件（消息数据）
LazyIndex offsetIndex;  // .index 文件（稀疏索引）
long baseOffset;           // 起始 Offset
}
// 稀疏索引条目（每条 8 字节）
class OffsetPosition {
int relativeOffset;        // 相对于 baseOffset 的偏移 (4 bytes)
int position;              // 在 .log 文件中的物理位置 (4 bytes)
}

1. 定位 Segment（TreeMap 查找）

• segments = [0, 367834, 735668, 1103502]

• floorEntry(500000) → baseOffset = 367834

• 找到文件：00000000000000367834.log

• 时间复杂度：O(log S)，S = Segment 数量（通常<100）

2. 索引二分查找（.index）

• relativeOffset = 500000 - 367834 = 132166

• 在 .index 二分查找 ≤ 132166 的最大条目

• 找到：[132100 → position=20500000]

• 时间复杂度：O(log N)，N = 索引条目数

3. 顺序扫描（.log）

• 从 position=20500000 开始顺序读，直到找到 offset=500000

• 最多扫描约一个索引间隔范围（默认 ~4KB 量级）

3.3HDFS vs Kafka 寻址设计对比

04 现代存储系统的演进：从能找到，到找得极致高效

• 需要支持复杂查询（不只是按 key/offset），不再是简单的按路径/按offset找数据，而是要支持多字段条件查询；
• 数据量从TB级到PB级，对象存储（如S3）成为主流，数据分布在多个文件，小文件+高频API调用的开销，成为新的性能瓶颈；
• 核心诉求从能找到数据，变成用最少的IO/API调用找到数据。

4.1 Milvus V1→V2：从「字段拆分」到「Segment整合」，减少文件数量就是最优解

1. 元数据查询

   从 etcd/MySQL 获取 Segment 列表 → [Segment 12345, 12346, 12347, ...]
   

2. 读取每个 Segment 的 id 字段

• 读取 12345/insert_log/100/*.binlog
  

• 读取 12346/insert_log/100/*.binlog
  

• ...

• 文件数：Segment 数 × id 字段的 binlog 数

3. 定位目标行

   在内存中找到 id=123
    所在的行号

4. 读取 vector 字段对应行

• 读取 vector 字段的 binlog 文件

• 文件数：Segment 数 × vector 字段的 binlog 数

文件数量从「N×字段数×binlog数」，直接降到「N（Segment数）」。

• 获取 Segment 列表 → [12345, 12346, ...]

• 获取 Row Group 统计信息
• 检查每个 Row Group 的 id 列 min/max
• id=123 可能在 Row Group 0（min=1, max=1000）

• 利用 Parquet 的列裁剪特性，只读取需要的列，跳过其他列
• 结合字段拆分设计，仅按需读取 id 字段文件、vector 大字段独立文件的目标 Row Group，无需读取全量数据

• 向量等大字段数据体量大，与小字段混存会压缩 Row Group 的承载行数，导致文件寻址、读取次数剧增；拆分后小字段 Row Group 可承载海量行数，大字段独立存储匹配，大幅提升读取效率。
• 单文件存储所有字段时，新增 / 删减列需要全量清洗、重写历史数据；拆分存储后，新增列仅需新增独立文件，删减列仅需屏蔽对应文件读取逻辑，无需改动历史数据，字段迭代灵活无额外开销。

4.2Iceberg：湖仓一体的终极寻址设计，分层元数据+统计剪枝，跳过95%的无效文件

1. 读metadata.json（1次IO）：获取当前快照和清单文件列表；
2. 读Manifest List（1次IO）：过滤掉无关分区（比如2023年的数据）；
3. 读Manifest Files（2次IO）：通过文件的统计信息（min/max date、min/max amount），过滤掉所有不满足条件的文件；
4. 读数据文件（3次IO）：只读取最终筛选出的3个文件。

05 四种存储系统寻址设计对比与共性总结

阅读推荐
熠智AI+Milvus:从Embedding 到数据处理、问题重写，电商AI客服架构怎么搭？
官宣 | Milvus 2.6云上GA：三层存储降本85% 、速度快ES 4-7 倍，多数据类型支持
官宣，Milvus开源语义高亮模型：告别饱和检索，帮RAG、agent剪枝80%上下文
不会做RAG、agent的本地数据管理？都来学Claude Code！附深度拆解
都有混合检索与智能路由了，谁还在给RAG赛博哭坟？