B+树是什么?

B+树是一种平衡多路查找树,它是B树的一种变体。B+树与B树的区别在于:

  • B+树的非叶子节点只存储键值和指针,不存储实际的数据,这样可以减少非叶子节点的大小,增加每个节点的分支数,降低树的高度。
  • B+树的所有叶子节点都存储了完整的数据记录,并且按照键值的大小顺序链接成一个链表,方便范围查询和顺序访问。
  • B+树的所有节点都有固定的大小,通常与磁盘块大小相同或者是其整数倍,这样可以最大化利用磁盘空间和减少磁盘I/O次数。

什么是B+树的内部节点和外部节点?

B+树的内部节点也可称为索引节点,叶子节点也可称为外部节点:

  • B+树的内部节点包括:Key键值,Index索引值
  • B+树的叶子节点包括:Key键值,Index索引值,Data数据

B+树有什么优点?

B+树作为一种索引数据结构,有以下几个优点:

  • B+树具有很高的扇出性(fanout),也就是说每个节点可以有很多个分支,这样可以使得树的高度很低,从而减少查找时需要访问的节点数。一般来说,B+树的高度在2~4层之间。
  • B+树可以有效地支持范围查询和顺序访问,因为它的叶子节点存储了完整的数据记录,并且按照键值排序链接成一个链表。这样可以避免回溯(backtracking)操作,也就是说不需要再回到上层节点去寻找下一个分支。
  • B+树可以充分利用磁盘预读(prefetching)功能,因为它的节点大小与磁盘块大小相同或者成倍数关系,这样可以一次性读取一个节点中的所有信息,减少磁盘I/O次数。

B+树与其他数据结构的对比

B+树作为一种索引数据结构,它与其他数据结构有什么优劣呢?我们来分别与二叉树、红黑树、哈希表进行对比。

  • 与二叉树和红黑树相比,B+树的优势在于它的高度更低,每个节点可以存储更多的键值和指针,因此可以减少查找时需要访问的节点数,降低磁盘I/O次数。而二叉树和红黑树的每个节点只能存储一个键值和两个指针,因此它们的高度更高,查找时需要访问更多的节点。
  • 与哈希表相比,B+树的优势在于它可以支持范围查询和顺序访问,因为它的叶子节点按照键值排序链接成一个链表。而哈希表是一种无序的数据结构,它只能支持精确匹配查询,不能支持范围查询和顺序访问。而且哈希表还需要解决哈希冲突的问题,当哈希冲突严重时,它的性能会下降。
  • 当然,B+树也有一些劣势,例如它需要维护平衡性,当插入或删除数据时,可能需要进行分裂或合并操作,这会增加磁盘I/O次数。而且B+树的空间利用率不是很高,因为每个节点都有一定的空间浪费。

InnoDB中B+树索引的特点

在InnoDB中,B+树索引分为聚簇索引和辅助索引两种类型。聚簇索引是按照主键来构造的B+树,其叶子节点存储了整张表的行记录信息。辅助索引是按照非主键来构造的B+树,其叶子节点存储了非主键值和对应的主键值。InnoDB中B+树索引有以下几个特点:

  • InnoDB中的数据是按照聚簇索引的顺序存储的,这样可以提高范围查询和聚合查询的效率。但是如果频繁插入或删除数据,可能会导致聚簇索引出现页分裂或页合并,影响性能。
  • InnoDB中只有聚簇索引的叶子节点存储了完整的行记录信息,而辅助索引只存储了主键值。这样可以减少辅助索引占用的空间,但是如果通过辅助索引来查询数据,需要先找到主键值,然后再通过聚簇索引来找到行记录信息,这就是所谓的回表操作,增加了磁盘I/O次数。
  • InnoDB中每个表都必须有一个聚簇索引,如果没有显式定义主键,则会选择第一个非空唯一列作为聚簇索引。如果没有这样的列,则会生成一个隐藏的6字节长的ROWID作为聚簇索引。因此建议在设计表时尽量定义一个合适的主键.

InnoDB中B+树索引的优化建议

根据InnoDB中B+树索引的特点,我们可以给出以下一些优化建议

  • 尽量选择较短的列作为主键,因为主键会被存储在辅助索引的叶子节点中,如果主键过长,会占用更多的空间,导致B+树的高度增加,影响查询效率。
  • 尽量选择自增的列作为主键,因为这样可以避免聚簇索引的页分裂和页合并操作,提高插入性能。如果主键是随机的或者是非空唯一列,那么每次插入数据都可能会导致聚簇索引重新调整结构,增加磁盘I/O次数。
  • 尽量避免使用select *查询,因为这样会导致辅助索引回表操作,增加磁盘I/O次数。应该只查询需要的列,并且尽量让这些列都被包含在辅助索引中,这样就可以直接从辅助索引中获取数据,不需要回表操作。
  • 尽量使用覆盖索引查询,覆盖索引是指一个查询语句所需的所有数据都能从一个索引中获取,不需要访问数据表。覆盖索引可以减少磁盘I/O次数,提高查询效率。可以通过explain命令查看查询是否使用了覆盖索引,如果extra列显示using index,则表示使用了覆盖索引。
  • 尽量利用前缀索引和索引下推优化查询,前缀索引是指只对字符串类型的列的前几个字符创建索引,这样可以节省空间,降低B+树的高度。但是前缀索引也有一些缺点,例如不能使用范围查询和like操作符。索引下推是指在辅助索引上进行where条件过滤,减少回表操作的次数。可以通过optimizer_switch参数开启或关闭索引下推功能。
  • 尽量避免在索引列上使用函数或表达式,因为这样会导致无法使用索引,降低查询效率。例如select _ from table where year(date) = 2020;就不能使用date列上的索引。应该改写为select _ from table where date between ‘2020-01-01’ and ‘2020-12-31’;这样就可以使用date列上的索引了。

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部