同步操作将从 flatfish/Java-Review 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
二叉树查找流程
左边二叉树的节点45左子树高度2,右子树高度0,左右子树高度差为2-0=2
在图二右边的AVL树上:
节点50的左子树高度为3,右子树高度为2,BF= 3-2 = 1;
节点45的左子树高度为2,右子树高度为1,BF= 2-1 = 1;
节点46的左子树高度为0,右子树高度为0,BF= 0-0 = 0;
节点65的左子树高度为0,右子树高度为1,BF= 0-1 = -1;
对于平衡二叉树,BF的取值范围为[-1,1]。如果发现某个节点的BF值不在此范围,则需要对树进行调整。
图中的 p 节点为指向子节点的指针,二叉查找树和平衡二叉树其实也有,因为图的美观性,被省略了。
图中的每个节点称为页,页就是我们上面说的磁盘块,在 MySQL 中数据读取的基本单位都是页,所以我们这里叫做页更符合 MySQL 中索引的底层数据结构。
从上图可以看出,B 树相对于平衡二叉树,每个节点存储了更多的键值(key)和数据(data),并且每个节点拥有更多的子节点,子节点的个数一般称为阶,上述图中的 B 树为 3 阶 B 树,高度也会很低。
基于这个特性,B 树查找数据读取磁盘的次数将会很少,数据的查找效率也会比平衡二叉树高很多。
假如我们要查找 id=28 的用户信息,那么我们在上图 B 树中查找的流程如下:
B+ 树和 B 树有什么不同:
聚集索引(聚簇索引):以 InnoDB 作为存储引擎的表,表中的数据都会有一个主键,即使你不创建主键,系统也会帮你创建一个隐式的主键。
这是因为 InnoDB 是把数据存放在 B+ 树中的,而 B+ 树的键值就是主键,在 B+ 树的叶子节点中,存储了表中所有的数据。
这种以主键作为 B+ 树索引的键值而构建的 B+ 树索引,我们称之为聚集索引。
非聚集索引(非聚簇索引):以主键以外的列值作为键值构建的 B+ 树索引,我们称之为非聚集索引。
非聚集索引与聚集索引的区别在于非聚集索引的叶子节点不存储表中的数据,而是存储该列对应的主键,想要查找数据我们还需要根据主键再去聚集索引中进行查找,这个再根据聚集索引查找数据的过程,我们称为回表。
select * from user where id>=18 and id <40
其中 id 为主键,具体的查找过程如下:
select * from xxx where name ="Jim";
name是非关键列,但是name同时也是索引列 - 非聚簇索引.
从图一中可以通过非聚簇索引列的值 -> 确定到该索引列值对应的主键值id.
***索引文件和数据文件是分开的.***B+树结构.
在 MyISAM 中,聚集索引和非聚集索引的叶子节点都会存储数据的文件地址。
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。