我读了几本书,参加了很少的关于数据库的培训,比如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树)索引通常是平衡的.这意味着无论在树中的哪个位置(O(log n)),查找值总是会花费相同的时间.通常,树中的级别数量是有限的,因此它倾向于“更宽”而不是“更深”.但是,对于小型数据集,维护和使用B树的成本可能不仅仅是读取所有行. B树索引适用于大型数据集,具有低选择性的数据集,或者您打算选择一系列对象而不仅仅是一个对象的数据集.
哈希表非常适合小型数据集.散列索引具有预定义数量的散列桶,具体取决于所使用的散列算法.这是因为给定的哈希算法只能产生如此多的唯一哈希值,所以它只能“更深”而不是“更宽”.一旦数据库引擎找到正确的存储桶,它就会遍历该存储桶中的所有对象以找到所需的存储桶.对于小的,高度选择性的数据集,每个桶包含非常少量的对象,并且很快就能得到解决.随着数据集越来越大,存储桶变得越来越拥挤.因此,如果您需要的对象位于小桶中或靠近桶的开头,则返回非常快.如果它在一个大水桶的末端,则需要更长的时间.索引不平衡,因此性能从O(1)到O(n).
声望
一般来说,我最常碰到B树.位图索引也是具有低基数的值的另一种选择(可以考虑布尔值或性别).这取决于您的数据库引擎,可用的索引类型.
Nosql的