这个问题其实还是很有趣的,我在上一篇文章中,写了:
1、为什么数据库索引不能用二叉排序树;
2、为什么数据库索引不能用红黑树;
本篇文章增加了:
1、为什么不能使用哈希表;
2、为什么不能使用B-树;
3、为什么能使用B+树。
一、为什么数据库的索引不能用二叉搜索树?
根据上面的演示,看着二叉搜索树也是可以的呀,也挺快嘛。
但是为什么用在数据库底层不合适呢?这也是面试时常问的。
我们可以演示一下:
https://www.cs.usfca.edu/~galles/visualization/BST.html
我们假设我们给Col1加上索引,那么依次对二叉搜索树插入:1、2、3、4、5、6、7;
可以看到退化成了一个链表的形式。
当我们查询7的话,时间复杂度就变成了单链表一样了。
从大到小也是:
总结如下:
- 如果数据库底层使用二叉搜索树的话,遇到数据为极端的情况下会退化成单链表,所以不太合适;
可以想象一下,如果我们给自增的一列使用二叉搜索树的索引数据结构的话,是不是就很倒霉了。这就是极端的情况,都在一边。
二、为什么红黑树不适合数据库索引?
红黑树又叫:二叉平衡树
红黑树作为Java开发人员应该很耳熟吧,JDK8中的HashMap中的底层数据结构就用到了红黑树。
这么牛逼的JDK中都用到了红黑树,为什么数据库中的索引数据结构不太适合呢?
还是上面那个假设,假设我们给Col1加上红黑树的索引。
过程如下动态演示:
如果我们执行:
select * from table1 where Col1 = 7;
- 1
动态演示如下:
可以看到,我们一共查询了4次就查到了。与没加这个索引之前还是有比较大的效果的,至少没有全部扫描。
总结:
通过观察可以看到,每次插入几乎都会去调整这颗二叉树,保持高度是平衡的。
如果数据量非常大的话,也是非常耗时的,所以红黑树也是不太合适。
三、为什么不能使用Hash数据结构作为索引的数据结构呢?
当你点进这篇文章的时候,肯定对于Hash表是熟悉的了。
Hash表的话,简单点说有这么几个特点:
- 1、数据插入的位置由哈希值决定,顺序无序的;
- 2、插入很快;
- 3、查找也很快;
我们拿一组数据来插入哈希表试试:
100、13、101、14、103、109
- 1
我们使用https://www.cs.usfca.edu/~galles/visualization/ClosedHash.html来动态模拟Hash表;
为了表现出来Hash表为什么不适用与数据库,我们顺序插入准备好的数据:
动态演示如下:
结果如下:
1、
我们在数据库中经常使用sql来查询一个范围的数据例如:
select * from t where id < 15;
- 1
我们知道哈希表是无序的,所以就凭借这一点,就比较困难。
心里应该也有数了,哈希表是肯定不可以的。
2、
从插入数据的动态演示中可以看到,100和13的哈希值都是13。
那么就会向后移动(这也是哈希表解决冲突的一种方式)。
例如:我们先插入100,然后插入13;
我们想查找13的话,就会比较慢了。
两个数可能体现不出来,1万个?10万个?100万个数呢?可想而知,就相当于进行了全表扫描。
所以,哈希表总体来说,不合适。
四、为什么不能使用B-树
B-Tree就是B树,不叫B减树。
我们继续来模拟:
https://www.cs.usfca.edu/~galles/visualization/BTree.html
插入1-10,10个数后:
B树确实解决了我们上面所说的哈希表的查找范围的问题。
我们执行下列sql:
select * from t where id > 5;
- 1
(1)首先查找到5
查找路径为:4–>6–>5;
(2)然后返回上一层查找到6
(3)然后查找到6
(4)…
可以看到会有一个回旋的过程,随着数据量的增长,回旋的过程也就越多,那么所浪费的时间也就越多。
五、为什么能使用B+树
我们使用这个来模拟:
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
构造一个1-10的数的B+树;
先来介绍以下这颗树:
一共分为两部分,叶子节点和非叶子节点。
- 叶子节点是由链表实现的,凡是插入的数据,全都链接在一起。
- 非叶子节点只存key;
- 叶子节点即存key又存value;
key:0-10这个数字;
value:0-10的数字的地址。
解决了B树中回旋查找的问题。查找效率也整体提高了。
例如:
select * from t where id > 5;
- 1
看下图:
可以看到,先查找非叶子节点5、然后7、然后6,最终查找到叶子节点5。
查找到之后,就可以顺序取出了,就不必继续回去上一层了。
文章来源: blog.csdn.net,作者:手撕代码八百里,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/qq_17623363/article/details/115029329