3、数据结构选型原则：时间复杂度、空间复杂度、缓存友好性、CPU缓存行对齐
做路由引擎这么多年，我踩过最大的坑，往往不是算法本身有多难，而是数据结构选型没想清楚。你想想看，一个路由表里存着几十万条路由，每次查表都要在微秒级完成。选错了数据结构，性能直接崩盘。
今天咱们就聊聊选型时的四个核心维度。说白了，就是时间、空间、缓存、对齐这四件事。
3.1 时间复杂度：别只看大O，要看常数
很多人一上来就盯着O(1)、O(log n)不放。我承认，大O很重要。但实际工程里，常数因子往往更致命。
举个例子。哈希表查找是O(1)，但计算哈希值、处理冲突的开销可不小。红黑树查找是O(log n)，但每次比较都是整数运算，常数极小。在路由前缀匹配这种场景下，我见过用红黑树反而比哈希表快的情况。
核心原则：选型时，先估算数据规模n的数量级。n小于1000时，O(n)的线性查找可能比O(log n)的树查找更快——因为CPU缓存命中率高。
我在项目中遇到过，有人非要把几百条路由塞进B+树里。结果呢？树的高度只有2层，但每次插入都要做节点分裂，开销远大于一个简单的数组+二分查找。嗯，这就是典型的「过度设计」。
3.2 空间复杂度：内存不是无限的
路由引擎跑在嵌入式设备上是常事。内存可能只有几十MB。你一个路由表吃掉一半，其他模块怎么办？
空间复杂度不只是「用了多少字节」这么简单。还要考虑：
- 指针开销：一个64位指针就是8字节。如果每个节点都带两个指针，100万条路由就是16MB的指针开销。
- 对齐填充：结构体成员之间的padding，有时候比数据本身还大。
- 内存碎片：频繁分配释放小对象，会导致内存碎片化，最终OOM。
我的习惯：优先用数组代替链表。数组是连续内存，没有指针开销，没有碎片问题。路由表用数组存储前缀，配合二分查找，空间利用率极高。
我曾经在一个项目里，把链表改成了数组+空闲索引池。内存占用从32MB降到了12MB，而且分配速度提升了3倍。说白了，连续内存就是香。
3.3 缓存友好性：让数据靠近CPU
这个点，很多人容易忽略。现代CPU的L1缓存只有32KB，L2缓存256KB，L3缓存几MB。如果你的数据结构导致频繁缓存未命中，性能会断崖式下跌。
为什么会这样？因为CPU从内存读数据，一次读一个缓存行（通常64字节）。如果你访问的数据分散在不同的缓存行里，CPU就得反复去内存取数据。一次缓存未命中，浪费几百个CPU周期。
怎么做到缓存友好？
- 数据紧凑排列：把经常一起访问的字段放在同一个结构体里，甚至同一个缓存行里。
- 顺序访问：遍历数组比遍历链表快得多，因为数组是顺序内存访问，预取器能提前加载。
- 减少间接跳转：指针链（比如链表、树）会导致随机内存访问，缓存命中率极低。
避坑指南：我曾经用链表实现路由前缀的LPM（最长前缀匹配）查找。结果性能测试时，每秒只能处理50万次查询。换成数组+二分查找后，直接飙到300万次。原因就是链表导致大量缓存未命中。
3.4 CPU缓存行对齐：别让数据跨行
缓存行对齐，说白了就是让你的数据不要跨两个缓存行。如果一个8字节的变量，恰好跨越了64字节的边界，CPU需要读两次内存才能拿到完整数据。
这在多线程场景下尤其重要。如果两个线程各自修改同一个缓存行里的不同变量，就会发生「伪共享」（False Sharing）。明明操作的是不同数据，但缓存一致性协议强制让两个核心来回同步缓存行，性能直接腰斩。
怎么处理？
- 结构体对齐：用
__attribute__((aligned(64)))或alignas(64)强制结构体按缓存行对齐。 - 填充padding：在多线程场景下，给每个变量后面加padding，确保不同线程的数据不在同一个缓存行里。
- 按缓存行大小分配：分配内存时，用
posix_memalign或aligned_alloc保证起始地址是64的倍数。
// 示例：缓存行对齐的结构体
struct route_entry {
uint32_t prefix; // 4字节
uint8_t prefix_len; // 1字节
// 这里会有3字节padding
uint32_t nexthop_id; // 4字节
// 为了对齐到64字节，手动填充
uint8_t padding[48]; // 填充到64字节
} __attribute__((aligned(64)));注意：缓存行对齐会浪费内存。每个结构体从32字节变成64字节，100万条路由就多占32MB。所以只在性能关键路径上用，别滥用。
3.5 四个维度的权衡
这四个维度不是独立的。你优化了时间，可能牺牲空间。你追求缓存友好，可能增加代码复杂度。实际选型时，得根据场景做权衡。
| 场景 | 优先考虑 | 推荐数据结构 |
|---|---|---|
| 路由查找（高频读） | 时间复杂度、缓存友好性 | 数组+二分查找、Trie树（压缩后） |
| 路由更新（高频写） | 时间复杂度、空间复杂度 | 红黑树、跳表 |
| 嵌入式设备（内存受限） | 空间复杂度、缓存行对齐 | 紧凑数组、位图 |
| 多线程并发 | 缓存友好性、伪共享避免 | 无锁队列、RCU保护的数组 |
我个人习惯是：先画一个简单的流程图，把数据访问模式、规模、性能要求列出来，再选型。别一上来就拍脑袋用哈希表或红黑树。
一个小技巧：在代码里埋性能计数器，统计缓存未命中次数、内存分配次数。用数据说话，比凭感觉选型靠谱得多。
3.6 知识体系总览
下面这张图，是我做路由引擎时总结的选型决策流程。你可以参考一下。
嗯，这张图的核心逻辑就是：先看数据访问模式，再看内存约束，最后结合缓存友好性做微调。别跳步骤，跳了容易翻车。
好了，这一章的内容就这些。记住，数据结构选型没有银弹。多测试、多对比、用数据说话，才是正道。