首页 >常见问题 > 正文

btree索引原理是什么

原创2020-07-01 09:34:260290
第12期线上培训班

btree索引原理即二叉树导致树高度非常高,逻辑上很近的节点,物理上非常远,无法利用局部性,IO次数多,查找效率低;Btree是一种平衡的“m-way”查找树,它可以利用多个分支节点来减少查询数据时所经历的节点数。

BTree索引原理

二叉树导致树高度非常高,逻辑上很近的节点,物理上非常远,无法利用局部性,IO 次数多,查找效率低

Btree是一种平衡的m-way查找树,它可以利用多个分支节点(子树节点)来减少查询数据时所经历的节点数,从而达到节省存取时间的目的。m称为B-Tree的度。

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

特点

  • 有一个根节点,根节点只有一个记录和两个孩子或者根节点为空;

  • 每个节点记录中的key和指针相互间隔,指针指向孩子节点;

  • d是表示树的宽度,除叶子节点之外,其它每个节点有[d/2,d-1]条记录,并且些记录中的key都是从左到右按大小排列的,有[d/2+1,d]个孩子;

  • 在一个节点中,第n个子树中的所有key,小于这个节点中第n个key,大于第n-1个key;

  • 所有的叶子节点必须在同一层次,也就是它们具有相同的深度;

  • 由于B-Tree的特性,在B-Tree中按key检索数据的算法非常直观:首先从根节点进行二分查找,如果找到则返回对应节点的data,否则对相应区间的指针指向的节点递归进行查找,直到找到节点或找到null指针,前者查找成功,后者查找失败。

推荐:《mysql教程

以上就是btree索引原理是什么的详细内容,更多请关注php中文网其它相关文章!

php中文网最新课程二维码
  • 相关标签:btree
  • 本文原创发布php中文网,转载请注明出处,感谢您的尊重!
  • 相关文章

    相关视频


    网友评论

    文明上网理性发言,请遵守 新闻评论服务协议

    我要评论
  • 专题推荐

    推荐视频教程
  • PHP+Jquery+Mysql实现省市县三级联动PHP+Jquery+Mysql实现省市县三级联动
  • MySQL权威开发指南(教程)MySQL权威开发指南(教程)
  • MySQL数据库技术小知识每日分享MySQL数据库技术小知识每日分享
  • MySQL高级进阶视频教程MySQL高级进阶视频教程
  • 视频教程分类