上个月做消息去重模块，我一开始用了教科书级的做法：链表实现LRU队列，存最近十万条消息ID。理由很简单，插入删除都是O(1)，逻辑也清楚。结果压测直接翻车，QPS卡在三千上不去。同事路过看了一眼，说改成固定大小的环形数组试试。我改完自己都有点懵——同样的机器，同样十万条上限，QPS飙到一万二。那一刻我第一反应是是不是测试脚本有问题，查了半个小时发现没有。
然后我开始看性能剖析的数据，才发现自己有多天真。链表每个节点都是malloc出来的，节点在内存里七零八落。CPU按64字节缓存行预取，你访问一个节点，周围那几十个字节大概率是别的对象，根本没用。而数组是一整块连续内存，CPU预取的每个缓存行里全是有效数据。就好比你去图书馆找书，链表是每次都要按索引卡跳去不同楼层，数组是把你要看的几十本书直接摊在一张桌子上。更坑的是malloc还有锁和分配器开销，尤其是多线程下，那玩意儿比遍历本身还贵。我用perf量了缓存未命中率，链表版本接近60%，数组版本只有不到5%。
后来我把项目里的索引部分从红黑树换成了有序数组加二分查找，效果同样出乎意料。数据量不到五百万条，每次查询只做大概二十次比较，但红黑树每次查询要走树高十二层左右，而且节点指针乱跳，缓存友好度远不如二分查找的连续数组。内存占用也降了，红黑树每个节点要存颜色、左右孩子、父节点指针，光额外字段就20多个字节，数组只用存键和值。当然我也不是全盘否定树结构——有频繁插入删除且需要维持顺序的时候，红黑树仍是有优势的，只是业务里绝大多数场景是读多写少，根本轮不到树的那些花活上场。
我突然意识到一件事：学校里讲的数据结构复杂度只是理想模型，它假设所有内存随机访问都一样快。但现实是CPU有多级缓存，内存有NUMA架构，磁盘有页和扇区。数据结构真正的胜负手往往不是操作步数，而是存储介质和访问模式是否匹配。比如B+树为什么在数据库里横着走？不是因为它的复杂度比红黑树好看，而是它的节点大小刻意设计成一个磁盘页或者一个内存页的大小，让一页能装尽可能多的键，减少IO次数。这就是工程对理论最好的修正。
说到底，我不觉得存在什么“最好”的数据结构，只存在“在这种数据规模、这个访问频率、这台机器的硬件条件下比较合适”的数据结构。如果非要给个建议，我会说先写个benchmark，用perf看缓存命中率，别一上来就掉书袋。数据结构得自己动手测一测，那些复杂度分析只能当参考。我吃了这次亏之后，现在选型第一句话就问：你的数据大概多大？是随机插还是追加？会不会整体删除？问完这三句话，答案基本已经出来了。