内存数据结构优化：红黑树 vs 跳表 vs 哈希表的选择、内存池与对象复用、缓存行对齐与伪共享

订单簿重建，说白了就是一场与延迟的赛跑。你想想看，每秒几万笔订单砸过来，你的数据结构要是慢了哪怕一微秒，整个系统就可能崩盘。今天咱们聊聊内存数据结构优化的三个核心问题：选什么数据结构、怎么管理内存、怎么让CPU缓存更高效。

红黑树 vs 跳表 vs 哈希表：到底选哪个？

这个问题我纠结过很久。刚入行那会儿，我觉得哈希表天下无敌——O(1)的查找速度，谁不爱？但后来在订单簿重建场景里栽了跟头。

哈希表的问题在于：它不支持范围查询。订单簿里经常要查"价格在100到105之间的所有订单"，哈希表就傻眼了。而且哈希冲突处理不好，性能会急剧下降。我个人习惯，只有在纯键值查找、没有排序需求时才用哈希表。

红黑树呢？它是平衡二叉搜索树，查找、插入、删除都是O(log n)。优点是支持范围查询，而且性能稳定。缺点是实现复杂，而且对CPU缓存不友好——节点在内存里是分散的，遍历时缓存命中率低。

跳表是我现在的主力。它用多层链表实现，查找也是O(log n)，但实现比红黑树简单多了。最关键的是，跳表的节点在内存里是连续存储的（如果你用数组实现），缓存命中率极高。我在项目中遇到过，把红黑树换成跳表后，订单簿重建时间从12微秒降到了7微秒。

内存池与对象复用：别再new/delete了

嗯，这里要注意。每次订单进来都new一个对象，处理完再delete——这种写法在低延迟系统里是自杀行为。为什么？因为内存分配器（比如malloc）本身就有锁，而且会产生内存碎片。

我建议用内存池。提前分配一大块连续内存，然后按固定大小切成块。每次需要对象时，直接从池里取一个空闲块，用完再还回去。整个过程没有系统调用，没有锁竞争。

// 一个简单的内存池示例
template<typename T>
class MemoryPool {
    char* pool;
    size_t block_size;
    std::vector<void*> free_list;
    
public:
    T* allocate() {
        if (free_list.empty()) {
            // 扩展池
            pool = new char[block_size * 1024];
            for (int i = 0; i < 1024; i++) {
                free_list.push_back(pool + i * block_size);
            }
        }
        void* ptr = free_list.back();
        free_list.pop_back();
        return new (ptr) T();  // placement new
    }
    
    void deallocate(T* ptr) {
        ptr->~T();  // 手动析构
        free_list.push_back(ptr);
    }
};

我曾经在一个项目中，用内存池把订单对象的分配时间从200纳秒降到了5纳秒。你想想看，每秒处理10万笔订单，光这一项就省了20毫秒——在低延迟系统里，这已经是天文数字了。

缓存行对齐与伪共享：CPU缓存才是真正的瓶颈

你以为内存访问很快？其实CPU缓存才是真正的性能杀手。现代CPU的L1缓存访问延迟只有几个纳秒，但主存访问延迟是几十纳秒。如果你的数据在缓存里，性能就能翻好几倍。

缓存行对齐是什么意思？CPU从主存加载数据时，一次加载64字节（一个缓存行）。如果你的数据刚好跨了两个缓存行，那就要加载两次，性能直接腰斩。

我习惯用alignas(64)来强制对齐：

struct alignas(64) Order {
    int64_t price;
    int64_t volume;
    int64_t timestamp;
    // 填充到64字节
    char padding[64 - 3 * 8];
};

伪共享更坑。两个线程各自修改不同的变量，但这两个变量恰好在同一个缓存行里。结果就是：线程A修改变量X，导致整个缓存行失效；线程B要修改变量Y，发现缓存行没了，只能重新加载。明明没有共享数据，却因为缓存行的原因互相拖累。

知识体系总览

下面这张图总结了内存数据结构优化的核心逻辑：

这三个方面不是孤立的。你选了跳表，但内存管理没做好，照样延迟高。你用了内存池，但缓存行没对齐，性能还是上不去。我个人的经验是：先选对数据结构（跳表优先），再优化内存管理（内存池+对象复用），最后做缓存对齐和伪共享防护。三步走完，订单簿重建延迟基本能控制在10微秒以内。

好了，这一章就聊到这儿。记住：在低延迟系统里，每一纳秒都很珍贵。选对数据结构、管好内存、对齐缓存——这三板斧砍下去，你的订单簿重建速度绝对能上一个台阶。