有序数列的数据结构优化
原文中文，约2700字，阅读约需7分钟。发表于：。在我们的 ecs 模块中，有一个重要的内部数据结构是 eid 的数组。它是 Component 结构的一部分，表示每个 Component 属于哪个 Entity 。目前，它是以一个有序的 id 数组实现的。 这个数据结构常见的操作分别是：遍历、随机访问、查找 id 所在的位置。一个有序数组可以很好的完成任务。O(1) 的随机访问时间，O(Log N) 的查找时间。 我们的 Entity...
本文讨论了实体ID的保存和内部数据结构的优化问题，介绍了使用间接索引和有序数组的方法。作者尝试了B树和跳表等优化方法，但最终放弃。对于实体数量较少的情况，直接使用2字节的内部ID即可。作者还提出了一种结合了B树和跳表思想的新的数据结构，通过分组和循环队列提高插入和删除效率。最后，作者用C语言实现了该数据结构并进行了性能测试。
