database - 数据库索引

Question

我需要开发用于分布式环境的数据库索引的“简单”实现。我对这个主题几乎一无所知，而且我有点被时间压力。

我很想听听关于这个主题的一些意见、例子和算法。我希望能够对我需要实现的内容有一个心理表征。

编辑：我指的是聚集索引

Answer 1

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

• 集群（即数据是物理组织的，如果需要，您可以在每次插入时重新排序）

  典型用例：物理组织通常与插入顺序相同，因此重新排序开销不是问题。例如，顺序 UID（数据库上下文中所谓的“IDENTITY”字段）就是这种情况

  聚集索引的一个明显缺点是您的数据只能有一个这样的索引。

  如果插入顺序恰好是排序顺序，则实现天真：使用列表。

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

• 非集群的（即你在数据上保留指针，就像在哈希表中一样）

  典型用例：集群不合适，因为它会导致很大的插入开销。

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

此处提供了与索引相关的广泛信息库

Answer 2

一个非常快速且易于实现、非常简单的索引实现，最适合任何具有本机关联数组格式的语言，是一个哈希，其键是您要索引的列的现有值，其值是数组具有该值的行的行 ID。