Linux内核

跳表(Skip List)深度实战:从随机层数、概率平衡到 Redis zset 与 LevelDB MemTable 的工程全解

跳表(Skip List)是 1989 年 William Pugh 在论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》里提出的一种**概率性平衡的有序数据结构**。它要解决的,是平衡二叉搜索树(AVL、红黑树、B 树)在工程里一个长期被忽视的痛点:**为了维持"平衡",它们不得不在每次插入删除时做复杂的旋转(rotatio…

字典树(Trie / 前缀树)深度实战:从字符沿边展开、压缩与双数组到 IP 路由与敏感词过滤的工程全解

前缀,是几乎所有"检索"类系统的隐形骨架:自动补全、搜索建议、T9 输入法、IP 路由的最长前缀匹配(LPM)、敏感词过滤、拼写纠错、词典树、前缀计数与排名……这些场景的共同点是——**查询的不是整条键,而是"以某串为前缀的所有键"**。当你发现自己在用 `startswith` 遍历百万字符串时,就该请出字典树了。

四叉树与八叉树深度实战:从空间递归划分的第一性原理、Morton 编码与范围查询,到碰撞检测、GIS 与三维场景管理的工程全解

空间数据无处不在:地图上的点、游戏里的碰撞体、点云中的三维坐标、图像里的像素块、甚至 NeRF/高斯泼溅里需要被快速检索的 3D 高斯。当数据规模从几百涨到几千万,朴素的两两比较(O(n²))会瞬间压垮系统。本文从第一性原理出发,把四叉树(Quadtree)与八叉树(Octree)这两种"把空间递归对半切"的结构讲透,并给出可直接落地的 Python 参考实现、复杂度对比与一份生产级陷阱清单。

Linux CFS 完全公平调度器深度工程实战:从红黑树到 vruntime 与组调度全链路

深度拆解 Linux CFS(Completely Fair Scheduler)调度器的核心机制与工程实践,涵盖虚拟运行时间 vruntime 计算、红黑树调度器内部结构、组调度(Group Scheduling)、NUMA 负载均衡、实时进程交互、cgroup 带宽控制、SCHED_IDLE/BATCH/ISO 策略选择,并结合 eBPF/ftrace 给出可观测与调优方法。