数据库索引

Question

我需要开发一个数据库索引的“朴素”实现，以便在分布式环境中使用。我对这个话题几乎一无所知，时间也让我感到有点压力。

我想听听关于这个问题的一些意见、例子和算法。我希望能够在精神上表达我需要实现的东西。

编辑:我指的是聚集索引的

Answer 1

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

• 群集(即数据是物理组织的，如果需要，可以在每次插入时重新排序)。 典型用例:物理组织通常与插入顺序相同，因此重新排序开销不是问题。例如，顺序UID(数据库上下文中所谓的"IDENTITY“字段)就是这种情况。 群集索引的一个明显缺点是数据上只能有一个这样的索引。 如果插入顺序恰好是排序顺序，则简单实现:使用列表。

1. Insertion is O(1) : you just append the new data of the list
2. Access is O(1) if the ID's are sequential (ie array indexes exactly matches UID), O(log) otherwise

​

• 非聚集(如Hashtable中的数据指针) 典型用例:集群不合适，因为它会导致较大的插入开销。

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

一个广泛的索引相关信息存储库是可用的这里。

Answer 2

一个非常快速且易于实现的、非常天真的索引实现，最适合于任何具有本机相联阵列格式的语言，它是一个散列，其键是您正在索引的列的现存值，其值是带有该值的行的行ID数组。