SQL INDEX - 它是如何工作的？

Question

我对数据库和SQL 的了解大部分是基于大学课程。无论如何，我在一家公司呆了几个月（将近一年），在那里我从事数据库工作。

我读过一些书，我已经在一些培训参加有关的数据库，例如MySQL，PostgreSQL，SQLite，Oracle和几个同样nonSQL dbS，从而我们MongoDB，Redis，ElasticSearch等。

就像我说的，我是初学者，很多知识缺乏，但今天有人说了一些完全违背我初学者知识的事情。

让我解释。让我们使用SQL数据库并创建一个Person包含少量记录的简单表：

id | name   | age
-----------------
1  | Alex   | 24
2  | Brad   | 34
3  | Chris  | 29
4  | David  | 28
5  | Eric   | 18
6  | Fred   | 42
7  | Greg   | 65
8  | Hubert | 53
9  | Irvin  | 17
10 | John   | 19
11 | Karl   | 23

现在，这是我想关注的部分 -id是INDEX.

到目前为止，我认为它是这样工作的：当一个表被创建时，它INDEX是空的。当我向表中添加新记录时，INDEX正在根据某些算法重新计算。例如：

一一分组：

1    ... N
N+1  ... 2N
     ...
XN+1 ... (X+1)N

所以，我以实例size = 11 elements和N = 3这将是这样的：

id | name   | age
-----------------
1  | Alex   | 24     // group0
2  | Brad   | 34     // group0
3  | Chris  | 29     // group0
4  | David  | 28     // group1
5  | Eric   | 18     // group1
6  | Fred   | 42     // group1
7  | Greg   | 65     // group2
8  | Hubert | 53     // group2
9  | Irvin  | 17     // group2
10 | John   | 19     // group3
11 | Karl   | 23     // group3

所以，当我使用查询时，SELECT * FROM Person WHERE id = 8它会做一些简单的计算8 / 3 = 2，所以我们必须在其中查找这个对象group2，然后将返回这一行：

8  | Hubert | 53

这种方法适用于时间O(k)在那里k << size。当然，按组组织行的算法肯定要复杂得多，但我认为这个简单的例子表明了我的观点。

所以现在，我想提出另一种方法，这是今天向我展示的。

让我们再次看一下这张表：

id | name   | age
-----------------
1  | Alex   | 24
2  | Brad   | 34
3  | Chris  | 29
4  | David  | 28
5  | Eric   | 18
6  | Fred   | 42
7  | Greg   | 65
8  | Hubert | 53
9  | Irvin  | 17
10 | John   | 19
11 | Karl   | 23

现在，我们正在创建类似于Hashmap（实际上，它是一个哈希映射）的东西，它映射id到address具有此 id 的行。让我们说：

id | addr 
---------
1  | @0001
2  | @0010
3  | @0011
4  | @0100
5  | @0101
6  | @0110
7  | @0111
8  | @1000
9  | @1001
10 | @1010
11 | @1011

所以现在，当我运行查询时： SELECT * FROM Person WHERE id = 8

它将直接映射id = 8到内存中的地址并返回该行。当然，这很复杂O(1)。

所以现在，我有几个问题。

1. 两种解决方案的优缺点是什么？

2. 在当前的数据库实现中，哪个更受欢迎？也许不同的数据库使用不同的方法？

3.它是否存在于非SQL数据库中？

先感谢您

---

比较

               |      B-tree     |   Hash Table
----------------------------------------------------
----------------   one element   -------------------
----------------------------------------------------
SEARCHING      |  O(log(N))      | O(1) -> O(N)  
DELETING       |  O(log(N))      | O(1) -> O(N)
INSERTING      |  O(log(N))      | O(1) -> O(N)
SPACE          |  O(N)           | O(N)
----------------------------------------------------
----------------    k elements   -------------------
----------------------------------------------------
SEARCHING      |  k + O(log(N))  | k * O(1) -> k * O(N)
DELETING       |  k + O(log(N))  | k * O(1) -> k * O(N)
INSERTING      |  k + O(log(N))  | k * O(1) -> k * O(N)
SPACE          |  O(N)           | O(N)

N - 记录数

我对吗？每次插入/删除后重建B 树和哈希表的成本如何？在B 树的情况下，我们必须更改一些指针，但在平衡 B 树的情况下，它需要更多的努力。同样在哈希表的情况下，我们必须做很少的操作，特别是如果我们的操作产生冲突。

Answer 1

您基本上是在描述 B 树索引和哈希索引。他们都有一个位置，但都最适合不同的工作。

的优点和缺点

B 树（和 B+ 树）索引通常是平衡的。这意味着无论它落在树中的哪个位置（O（log n）），寻找一个值总是需要相同的时间。一般来说，树中的层数是有限的，所以它往往会变得“更宽”而不是“更深”。然而，对于小数据集，维护和使用 B 树的成本可能不仅仅是读取所有行。B 树索引适用于大型数据集、低选择性数据集或您打算选择一系列对象而不仅仅是一个对象的数据集。

哈希表非常适合小数据集。哈希索引具有预定义数量的哈希桶，具体取决于所使用的哈希算法。这是因为给定的散列算法只能产生这么多唯一的散列，所以它只会变得“更深”而不是“更广”。一旦数据库引擎找到了正确的存储桶，它就会遍历该存储桶中的所有对象以找到您想要的对象。对于小型、高度选择性的数据集，每个桶包含的对象数量非常少，并且可以很快解决。对于更大的数据集，存储桶会变得更加拥挤。因此，如果您需要的对象在一个小桶中或靠近桶的开头，它会很快返回。如果它位于大桶的末端，则需要更长的时间。索引不平衡，因此性能从 O(1) 到 O(n) 不等。

人气

一般来说，我遇到的 B 树最多。位图索引也是基数较低的值的另一种选择（想想布尔值或性别）。这将根据您的数据库引擎关于可用索引类型而有所不同。

无SQL

NoSQL 数据库肯定支持索引。大多数支持 B 树或 B 树的变体。大多数似乎也支持散列索引。