我需要开发一个“简单”的数据库索引实现,以便在分布式环境中使用。我对这个主题几乎一无所知,而且我有点时间压力。
我很想听听有关该主题的一些意见、示例和算法。 我希望能够对我需要实现的内容有一个心理表征。
编辑:我指的是聚集索引
最佳答案
基本上有两种主要类型的索引:
集群(即数据是物理组织的,如果需要,您可以在每次插入时重新排序)
典型用例:物理组织通常与插入顺序相同,因此重新排序开销不是问题。例如,顺序 UID(数据库上下文中所谓的“IDENTITY”字段)就是这种情况
聚簇索引的一个明显缺点是您的数据只能有一个这样的索引。
如果插入顺序恰好是排序顺序,则简单实现:使用列表。
- 插入是 O(1) :您只需附加列表的新数据
- 如果 ID 是连续的(即数组索引与 UID 完全匹配),则访问为 O(1),否则为 O(log)
Unclustered(即你在数据上保留指针,就像在 Hashtable 中一样)
典型用例:集群不合适,因为它会导致很大的插入开销。
根据您的需要,您可能最终会使用这两种数据结构
索引相关信息的广泛存储库可用here
关于数据库索引,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/682762/