php pdf xamarin vue安装教程 git视频教程 纯html网页模板 jq获取最后一个子元素 ps字体旋转角度 oracle删除表字段 a标签去除下划线 css面试题 cad正在执行命令 python下载安装教程 python打开文件夹 java重载和重写 javafinally java时间函数 javastring类型 java的方法 java数组最大值 linux远程 灼热峡谷 id解锁大师 销售单软件 cg模宝 刷机工具下载 wine模拟器 dota改键工具 摩斯密码翻译器 存储过程写法 博途v14安装教程 扫微信二维码诈骗原理 kafka权威指南 facetime要钱吗 oracle游标 分割字符串 wps苹果电脑版 ps虚化背景 点状字体 如何删除注册表
当前位置: 首页 > 学习教程  > 编程语言

了解Mysql索引底层原理,理解索引如何支持千万级表的快速查找?

2020/8/11 18:49:50 文章标签:

定义

B 树可以看作是对2-3查找树的一种扩展,即他允许每个节点有M-1个子节点。

  • 根节点至少有两个子节点
  • 每个节点有M-1个key,并且以升序排列
  • 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
  • 其它节点至少有M/2个子节点

B+树是对B树的一种变形树,它与B树的差异在于:

  • 有k个子结点的结点必然有k个关键码;
  • 非叶结点仅具有索引作用,跟记录有关的信息均存放在叶结点中。
  • 树的所有叶结点构成一个有序链表,可以按照关键码排序的次序遍历全部记录。

B+ 树的优点在于:

  • 由于B+树在内部节点上不包含数据信息,因此在内存页中能够存放更多的key。 数据存放的更加紧密,具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。
  • B+树的叶子结点都是相链的,因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连,所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻,所以缓存命中性没有B+树好。

但是B树也有优点,其优点在于,由于B树的每一个节点都包含key和value,因此经常访问的元素可能离根节点更近,因此访问也更迅速。

 

 


本文链接: http://www.dtmao.cc/news_show_100027.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?