美文网首页
B树和B+树——应用于数据库索引

B树和B+树——应用于数据库索引

作者: XDgbh | 来源:发表于2018-08-01 21:22 被阅读160次

多路查找树——相比于常用的二叉树,多路查找树每个节点可以存储多个元素和多个孩子指针。主要用于做索引,来降低程序对外存磁盘设备上的数据的访问次数。

  • 【2-3树】
    树中每个结点要么是2结点(即1个元素和2孩子指针或2NULL),要么是3结点(即2个元素和3个孩子指针或3NULL)。
  • 【2-3-4树】
    2-3树的扩展,增加了4结点的使用。树中每个结点要么是2结点(即1个元素和2孩子指针或2NULL),要么是3结点(即2个元素和3个孩子指针或3NULL),要么是4结点(即3个元素和4个孩子指针或4NULL)。
  • 都要保证所有的叶子节点都在同一层次上,即保证平衡。因此每次插入和删除结点后,都可能要对叶子节点进行调整。

B树

B树结构做索引怎么就能降低程序对外存磁盘设备上的数据的访问次数呢?

B+树——对B树的改进,使得更适用于文件系统和数据库。


【B树示例】

【B+树示例】
  • 可以看到,B+树的每个分支结点中只保存了索引值,而没有保存实际的数据值。这就使得每个结点(内存页面)可以存放更多个索引元素,进一步降低了树的高度,提高了查询的效率。
  • 对于B树在遍历所有元素时有重复的缺陷,B+树只要从叶子节点从左往右遍历一遍就可以,不会发生重复。

B+树作为数据库索引的实例,其中0x56等为数据实际地址

为第一列数据做索引
为第二列数据做索引

数据库索引优化策略

  • 高效使用索引的首要条件是知道什么样的查询会使用到索引,即查询语句要满足B+Tree中的“最左前缀原理”时,才会使用到已经创建的索引。

  • 既然索引可以加快查询速度,那么是不是只要是查询语句需要,就建上索引?答案是否定的。因为索引虽然加快了查询速度,但索引也是有代价的:索引文件本身要消耗存储空间,同时索引会加重插入、删除和修改记录时的负担,另外,MySQL在运行时也要消耗资源维护索引,因此索引并不是越多越好。一般两种情况下不建议建索引。
    第一种情况是表记录比较少。
    第二种不建议建索引的情况是索引的选择性较低。所谓索引的选择性(Selectivity),是指不重复的索引值与表记录数的比值。越接近于1说明索引值唯一性越好,这对于B+树的维护和查询效率都很好。

  • 有一种与索引选择性有关的索引优化策略叫做前缀索引,就是用列的前缀代替整个列作为索引key,当前缀长度合适时,可以做到既使得前缀索引的选择性接近全列索引,同时因为索引key变短而减少了索引文件的大小和维护开销。

详细的MySQL数据库索引原理和优化看这篇博文:http://blog.codinglabs.org/articles/theory-of-mysql-index.html

相关文章

  • MySQL系列-InnoDB索引

    B+树索引 B+树索引就是传统意义上的索引,这是目前关系型数据库系统中查找最为常用的和最为有效的索引。 B+树的结...

  • 【恋上数据结构与算法二】(十一)B+树

    B+树 ◼ B+树是B树的变体,常用于数据库和操作系统的文件系统中MySQL数据库的索引就是基于B+树实现的 ◼ ...

  • B+

    B+树 B+树是B树的变体,常用于数据库和操作系统的文件系统中,如MySQL数据库的索引就是基于B+树实现的 B+...

  • 《高性能Mysql》-第五章-创建高性能的索引

    1.b-树索引 索引首先要回顾一下b树b+树的特点和区别,数据库引擎用b+树的好处有查询时间比较稳定,b+树比较适...

  • BoltDB(二)page 结构

    B+ 树模型 要明白 B+ 树模型,可以参考:MySQL 数据库索引 -- B+树模型[https://www.j...

  • B与B+树

    B+树更加适合在区间查询的情况,B+树常用于数据库索引,而B树则常用于文件索引。 B树: 树的总体结构: 特点: ...

  • 31-B+树

    B+树 B+树是B树的一种变体,常用语数据库和操作系统的问题件系统中 MySQL数据库的索引就是基于B+树实现的 ...

  • 深入理解Mysql索引底层数据结构与算法学习笔记

    笔记链接 没有,只有一个ppt 目录 索引构建红黑树,hash, b树,b+树详解 千万级数据库表如何用b+树索引...

  • MySQL中B+Tree索引原理(摘选)

    B+树索引是B+树在数据库中的一种实现,是最常见也是数据库中使用最为频繁的一种索引。B+树中的B代表平衡(bala...

  • Mysql索引BTree、B+Tree详细分解

    B+树索引是B+树在数据库中的一种实现,是最常见也是数据库中使用最为频繁的一种索引。B+树中的B代表平衡(bala...

网友评论

      本文标题:B树和B+树——应用于数据库索引

      本文链接:https://www.haomeiwen.com/subject/rubrvftx.html