SQL INDEX – 它是如何工作的?

前端之家收集整理的这篇文章主要介绍了SQL INDEX – 它是如何工作的?前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我对数据库sql的了解主要基于大学课程.无论如何,我在公司里花了很少的钱(差不多一年),我在那里工作数据库.

我读了几本书,参加了很少的关于数据库的培训,比如MySQL,Postgresql,sqlite,Oracle以及很少的非sql dbs,比如MongoDB,Redis,ElasticSearch等.

就像我说的那样,我很缺乏知识,但是今天,有人告诉了一些事情,这完全违背了我的乞讨者的知识.

让我解释.让我们采用sql数据库并创建简单的表,其中包含很少的记录:

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为空.当我在表中添加新记录时,根据一些alghortims重新计算INDEX.例如:

逐个分组:

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

所以,对于我的大小= 11元素和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 <<<尺寸.当然,组织行分组的alghoritm肯定要复杂得多,但我认为这个简单的例子显示了我的观点. 所以现在,我想提出另一种方法,今天已经向我展示了这种方法. 我们再来看一下这张桌子:

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映射到具有此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.哪一个在当前的数据库实现中更受欢迎?也许不同的dbs使用不同的方法

3.它是否存在于非sql dbs中?

先感谢您

对比

|      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树的情况下它需要更多的努力.同样在Hash表的情况下,我们必须做很少的操作,特别是如果我们的操作产生冲突.

解决方法

您基本上是在描述B树索引和哈希索引.他们都有一个地方,但两者最适合不同的工作.

的优点和缺点

B树(和B树)索引通常是平衡的.这意味着无论在树中的哪个位置(O(log n)),查找值总是会花费相同的时间.通常,树中的级别数量是有限的,因此它倾向于“更宽”而不是“更深”.但是,对于小型数据集,维护和使用B树的成本可能不仅仅是读取所有行. B树索引适用于大型数据集,具有低选择性的数据集,或者您打算选择一系列对象而不仅仅是一个对象的数据集.

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

声望

一般来说,我最常碰到B树.位图索引也是具有低基数的值的另一种选择(可以考虑布尔值或性别).这取决于您的数据库引擎,可用的索引类型.

Nosql

Nosql数据库肯定支持索引.大多数支持B树或B树的变种.大多数似乎也支持散列索引.

原文链接:https://www.f2er.com/mssql/79431.html

猜你在找的MsSQL相关文章