原 mysql的索引为什么是B+树?
版权声明:本文为博主原创文章,请尊重他人的劳动成果,转载请附上原文出处链接和本声明。
本文链接:https://www.91mszl.com/Dream/article/details/1199
一:为什么不是hash?
答:hash一次就能找到对应的数据,但是hash无法进行范围查询和排序操作。
二:二叉树。
二叉树的特点:
1. 一个节点只能有两个子节点,也就是一个节点上不能超过2个。
2. 左子节点小于本节点,右子节点大于本节点。比我大的向右,比我小的向左。
为什么mysql不实用二叉树呢?
答:二叉树无法解决树向一边倒的问题。如当数据为连续的时候,树会不平衡,树会向左边或右边一直连续下去。如下图所示,要查询007这条数据,需要查找7次才能找到,这几乎是要命的。
二叉树动态演示地址:
https://www.cs.usfca.edu/~galles/visualization/BST.html三:平衡二叉树(AVL)。
平衡二叉树的结构
平衡二叉树不会存在左或右倾斜的情况,但是如上图所示如果我要查找0015这条数据,需要查询4次,如果数据越多,那么树就越高,树越高查询的次数就越多。
平衡二叉树动态演示地址:
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html四:B树。
B树的结构
B树的树高是3。
B树动态演示地址:
https://www.cs.usfca.edu/~galles/visualization/BTree.html五:B+树。
B+树结构
1) B+上面是B树,下面是链表。方便范围查找,排序。
2) B+树非叶子节点只存储键值信息。所有叶子节点之间都有一个链指针。数据记录都存放在叶子节点中。
B+树动态演示地址:
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html2020-04-03 20:11:51 阅读(750)
名师出品,必属精品 https://www.91mszl.com
博主信息