数据库索引

Question

我需要开发一个"天真"的数据库索引实现,以便在分布式环境中使用.我对这个问题几乎一无所知,而且我对时间有点压力.

我很想听听有关这个主题的一些意见,例子和算法.我希望能够对我需要实现的内容进行心理表达.

编辑:我指的是聚簇索引

Answer 1

基本上有两种主要类型的索引:

• 聚集(即数据是物理组织的,如果需要,您可以在每次插入时对其进行重新排序)

  典型用例:物理组织通常与插入顺序相同,因此重新排序开销不是问题.这是例如顺序UID的情况(数据库上下文中所谓的"IDENTITY"字段)

  聚簇索引的一个明显缺点是,您的数据只能有一个这样的索引.

  如果插入顺序正好是排序顺序,则执行Naive:使用List.

  1. 插入是O(1):您只需附加列表的新数据
  2. 如果ID是顺序的(即数组索引与UID完全匹配),则访问为O(1),否则为O(log)

• Unclustered(即您在数据中保持指针,如在Hashtable中)

  典型的用例:聚类不合适,因为它会导致很大的插入开销.

根据您的需要,您可能最终会使用这两个数据结构

此处提供了大量与索引相关的信息库