【Mysql索引】二叉树、红黑树、B树、B+树
【Mysql索引】二叉树、红黑树、B树、B+树
索引是帮助Mysql高效获取数据的排好序的数据结构
(1)哈希表
Select * from t where t = 5;
上面的语句先到哈希表中找到索引,索引表里存放着对应的地址;然后根据哈希表里的地址,到二叉树里查找,二叉树的查找会快一点。二叉排序树是左小右大,通过比较值大小来往下查找
但是索引基本不用二叉树,为什么不用二叉树呢?
(2)二叉树的弊端的演示:
一个学习算法很好用的网站:算法演示网站
发现问题所在,但我们插入一个有序的数列时,二叉树就会退化为一个链表,这样二叉树的检索优势就不存在了,因此不能使用二叉树,二叉树改进成 B 树
(3)红黑树的插入演示:
当一棵子树的高度差超过2的时候,红黑树通过自旋,把中间那个往上提,把第一个往下放,变成左右子树高度差为0,这样就能避免二叉树退化成链表了
但是红黑树还是有点问题,此时用红黑树存放100万个数据,把树放满,这个树的高度会越变越高,这样的话查找的效率也会大大降低,所以红黑树只是在HashMap中使用,而不能用来处理大量的数据。这时候就要考虑在数据增多的时候而不增加树的高度,来看B树
(4)B树的演示
即使是百万数据,想把数据查找的次数控制在3-5之间,也就是说树的高度控制在3-5之间。
那么就把树的每一层变大一点,放的节点多一点,这样树的高度就会控制好,我们设置每一个节点最多放3个数据,
看一下B树存放索引的数据结构:加入搜索20,先从第一层找,把搜索值和15比较,然后往右去跟56比较,然后就能确定在15-56之间的位置,就可以到第二层搜索,找到!
(5)B+树的演示:(叶子加指针:支持范围查找)
B+树也叫多叉平衡树
一次检索6的过程:
B+树存放索引的情况:
1-非叶子节点不存储data,只存储索引(冗余),可以放更多的索引
2-叶子节点包含所有的索引字段
3-叶子节点用指针连接,提高区间访问的性能
InnoDB引擎下的B+树索引,第一层的节点为16Kb,而第一层的15节点站8b,15-56之间的节点的长度为6b,这个白色节点表示下一层的指针,也就说存储一个索引为14b。所以每一层可以放置1170个索引,那么三层B+树可以放置1170117016=2190万个索引。注意15节点下面没有存放data,这只是一个冗余索引,帮助你到叶子节点中去找具体的data。
注意到B+树还有一个改进,那就是叶子节点加了横向指针。因为B+树的叶子节点是排好序的,
(7)学习MyISAM引擎的索引的底层原理
MyISAM引擎创建的表分为三个文件,分别是:
- frm后缀:表定义的一些内容
- MYD后缀:MyISAM引擎对应的Data,也就是数据文件
- MYI后缀:MyISAM引擎对应的Index,也就是索引文件
所以说,MyISAM引擎的索引文件和数据文件是分离的,从数据结构看叶子节点里放的不是data,放的是地址,找到地址后再到数据文件里找数据
(8)学习InnoDB引擎(聚集索引)
InnoDB引擎创建的表分为两个:
1-frm后缀:表定义的内容
2-ibd后缀:存储索引和数据的文件
1-表数据文件本身就是按B+树组织的一个索引结构文件
2-聚集索引:索引文件和数据文件不分离,都放在叶子节点里
3-为什么InnoDB表必须有主键,并且推荐使用整型的自增主键?
InnoDB必须要有主键,并且使整型的自增主键。如果你没有创建主键的话,InnoDB引擎会在表中找一个能唯一标识的数据自动为你创建主键。使用整型是因为整型的数字2<3比较的速度很快,比使用UUID这种字符的比较快很多,字符还需要转换成ACSII码,然后才进行比较;使用自增主键作为索引,而索引放在叶子节点中,叶子节点之间有个指针,叶子指针节点是一个递增的趋势,所以指针可以快速找到下一个节点,这个指针可以有效的支持范围查找,但是如果不是自增的话就不好进行范围查找了。
4-为什么非主键索引结构叶子节点存储的是主键值?(一致性和节省存储空间)
(9)哈希索引和B+树索引(叶子节点指针的作用:支持范围查找)
哈希索引用的非常少,多数用的就是B+树索引,用哈希索引的速度是比B+树索引要快的,但是它有一个致命的缺点:
select * from table Where col = 6;如果用哈希索引,那就直接到哈希索引表里找就行了,速度很快
但是如果加上检索的范围 select * from table Where 6<col<9;,检索结果集再用哈希索引就不行了,而且工作中肯定离不开范围查找,使用B+树索引进行范围查找的时候,就可以用到叶子节点的指针,先在叶子节点中快速定位到6,然后根据叶子节点的指针往后找到9,那么指针经过的所有叶子节点就是要查找的范围结果集,