有序数列的数据结构优化
💡
原文中文，约2700字，阅读约需7分钟。
📝
内容提要
本文讨论了实体ID的保存和内部数据结构的优化问题，介绍了使用间接索引和有序数组的方法。作者尝试了B树和跳表等优化方法，但最终放弃。对于实体数量较少的情况，直接使用2字节的内部ID即可。作者还提出了一种结合了B树和跳表思想的新的数据结构，通过分组和循环队列提高插入和删除效率。最后，作者用C语言实现了该数据结构并进行了性能测试。
🎯
关键要点
-
讨论了实体ID的保存和内部数据结构的优化问题。
-
使用间接索引保存24bit ID以节省空间。
-
有序数组实现了O(1)的随机访问和O(Log N)的查找时间。
-
尝试了将数据按固定32或256个元素分组的优化方法。
-
最终放弃了复杂的实现，因实际Entity数量较少。
-
考虑到插入和删除效率低，提出了优化方案。
-
B树和跳表是经典的插入和删除优化方法。
-
设计了一种结合B树和跳表思想的新数据结构。
-
新结构通过分组和循环队列提高插入和删除效率。
-
支持致密型和稀疏型分组以管理不同类型的ID。
-
用C语言实现了该数据结构并进行了性能测试，随机访问效率与平坦数组相当。
➡️
