存储结构：稀疏集 (Sparse Set)

在上一章中，我们得出结论：为了极致的性能，ECS 必须在底层采用连续的数组（SoA）来存储组件。但是，如果我们非常“死板”地使用大数组来存储组件，会面临一个严重的内存浪费问题。

1. 数组索引的困境

假设我们用实体的 ID（比如范围在 0 ~ 9999）作为直接索引（Index），在一个长度为 10000 的大数组中存储 PlayerScore 组件。

如果这个世界里只有 3 个真正的玩家（实体 ID 分别为 1, 50, 9000），其他的 9997 个实体都是没有分数的树木或石头。那么我们的数组将会长这样：

Score 数组: [Null, Score_1, Null, ..., Score_50, Null, ..., Score_9000, ...]

这不仅造成了惊人的内存空间浪费（9997 个空洞），更致命的是它彻底破坏了连续遍历的性能，CPU 会被迫将大量的“空洞（Null）”加载进缓存中，引发灾难性的 Cache Miss。

如何做到既能用 O(1) 的时间复杂度通过 Entity ID 找到组件，又能保证真正存储组件的数组是百分之百紧凑、没有任何空洞的？

稀疏集（Sparse Set）应运而生。它是 C++ 知名 ECS 框架 EnTT 的基石数据结构。

2. 稀疏集的双数组结构

稀疏集的核心思想是用内存空间换取时间和连续性。它由两个数组组成：

1. 稀疏数组 (Sparse Array)：一个用来当“黄页簿”的巨大数组，其索引就是 Entity ID。它的里面存的是什么？存的是该组件在密集数组中的真实索引。
2. 密集数组 (Dense Array)：一个只有真实数据、绝对紧凑排列的小数组。它真正按照添加顺序存储着组件的内容（或者实体 ID）。

我们来看一个具体的运作图景。还是刚才的例子，实体 1、50、9000 拥有 Score 组件。稀疏集的状态如下：

// 稀疏数组 (索引代表实体 ID，内容指向密集数组的位置，-1 代表无)
Sparse[0]    = -1
Sparse[1]    =  0   <-- 实体 1 的组件在 Dense 的 0 号位
...
Sparse[50]   =  1   <-- 实体 50 的组件在 Dense 的 1 号位
...
Sparse[9000] =  2   <-- 实体 9000 的组件在 Dense 的 2 号位

// 密集数组 (绝对连续，没有任何空洞)
Dense[0] = Score_1
Dense[1] = Score_50
Dense[2] = Score_9000

3. O(1) 的增删查改

稀疏集之所以在 ECS 中大放异彩，是因为它做到了所有基础操作的时间复杂度都是极为廉价的 O(1)。

• 查询 (Query)：你想查询实体 50 的分数？ 第一步：查黄页，得知 DenseIndex = Sparse[50]，结果是 1。 第二步：去密集数组取数据，return Dense[1]。 （常数级时间，没有任何循环搜索！）
• 添加 (Add)：给实体 10 添加一个新分数。 第一步：把 Score_10 追加到密集数组的最后面 Dense[3] = Score_10。 第二步：更新黄页记录，令 Sparse[10] = 3。
• 遍历 (Iterate)：这是 System 最常用的操作。 由于密集数组是绝对紧凑排布的，这简直是 CPU 缓存的最爱。System 直接写一个 for 循环遍历整个 Dense 数组即可，缓存命中率直接拉满。根本不需要去理会那个有无数空洞的 Sparse 数组。

4. 巧妙的 O(1) 删除：Swap and Pop

删除操作是展现稀疏集智慧的高光时刻。如果在数组中间挖去一个数据，通常有两种做法： 一种是把后面的数据全部往前挪一格（时间复杂度 O(N)，对于底层框架这是无法忍受的慢）。 另一种是留下一个空洞，但这又破坏了内存的连续性。

稀疏集的做法被称为 Swap and Pop（交换并弹出）。

假设我们要删除上面例子中的实体 50 的组件（它在 Dense[1] 的位置）：

1. 找到 Dense 数组中最后一个元素（这里是 Score_9000，位于 Dense[2]）。
2. 将这最后一个元素，覆盖到想要删除的位置：也就是令 Dense[1] = Dense[2]。
3. 更新对应实体的黄页：将实体 9000 的黄页指向新位置 Sparse[9000] = 1。
4. 将密集数组的长度减 1（即 Pop，丢弃了末尾那个已经被复制走的值，同时把 Sparse[50] 设为 -1 标记为不可用）。

整个过程只需执行一次赋值和指针更新。原本在中间的空洞被填补了，数组再次恢复了完美的紧凑状态！这正说明了为什么在 ECS 中，实体的处理顺序是无法得到保证的（因为随着组件的不断增删，实体在密集数组里的物理顺序每时每刻都在像洗牌一样跳跃）。

5. 稀疏集的局限与多组件查询的痛点

稀疏集如此优秀，为何有些框架（比如 Unity DOTS）没有大规模采用它，而是使用了更复杂的原型（Archetype）结构？

问题出在多组件的交叉查询上。

当我们需要同时遍历包含 [Position, Velocity] 这两个组件的实体时，稀疏集怎么做？ 它需要分别拿出 Position 的稀疏数组和 Velocity 的稀疏数组。由于同一个实体在不同组件的密集数组里的索引位可能完全不一样，引擎被迫做如下操作：

1. 遍历较小的那个密集数组（比如 Velocity）。
2. 对每个元素，去反查它的实体 ID。
3. 利用实体 ID 去查 Position 的稀疏数组。
4. 如果查到了结果，说明该实体确实同时拥有两个组件，然后再跳到 Position 的密集数组中读取它的位置数据。

可以看到，当同时要求读取多个组件时，稀疏集的运作又在底层引发了一定程度的指针追逐（Pointer Chasing），破坏了一部分连续读取的红利。

为了解决多组件严格对齐的问题，业界搬出了 ECS 领域的终极形态：原型模式 (Archetype)。我们将在下一章详细解析。