MySQL的索引,为什么是B+而不是平衡二叉树

栏目: IT技术 · 发布时间: 4年前

内容简介:讲到索引,第一反应肯定是能提高查询效率。例如书的目录,想要查找某一章节,会先从目录中定位。如果没有目录,那么就需要将所有内容都看一遍才能找到。索引的设计对程序的性能至关重要,若索引太少,对查询性能受影响;而如果索引太多,则会影响增/改/删等的性能。MySQL中一般支持以下几种常见的索引:

数据库为什么使用B+树?

前言

讲到索引,第一反应肯定是能提高查询效率。例如书的目录,想要查找某一章节,会先从目录中定位。如果没有目录,那么就需要将所有内容都看一遍才能找到。

索引的设计对程序的性能至关重要,若索引太少,对查询性能受影响;而如果索引太多,则会影响增/改/删等的性能。

知识点

MySQL中一般支持以下几种常见的索引:

B+树索引
全文索引
哈希索引

我们今天重点来讲下B+树索引,以及为什么要用B+树来作为索引的数据结构。

B+树索引并不能直接找到具体的行,只是找到被查找行所在的页,然后DB通过把整页读入内存,再在内存中查找。

1. 与二叉树相比

二叉树相比于顺序查找的确减少了查找次数,但是在最坏情况下,二叉树有可能退化为顺序查找。而且就二叉树本身来说,当数据库的数据量特别大时,其层数也将特别大。二叉树的高度一般是log_2^n,B树的高度是log_t^((n+1)/2) + 1,其高度约比B树大lgt倍。n是节点总数,t是树的最小度数。

2. 与B树相比

B树在提高IO性能的同时,并没与解决元素遍历时效率低下的问题,正是为了解决这个问题,B+数应运而生。B+数只需遍历叶子节点即可实现整棵树的遍历,而B树必须使用中序遍历按序扫库,B+树支持范围查询非常方便。这才是数据库选用B+树的主要原因。

另外,最后说一下,并不是说B+树就比B树好,有很多基于频率的搜索是选用B树,越频繁query的结点越往根上走,前提是需要对query做统计,而且要对key做一些变化。

无论是B树还是B+树由于前边几层反复query,因此早已被加载入内存,不会出现读磁盘IO。一般启动的时候,就会主动换入内存。在内存中B+树并没有优势,只有在磁盘中B+树的威力才能显现。

采用B+树的索引结构优点:

B+树的高度一般为2-4层,所以查找记录时最多只需要2-4次IO,相对二叉平衡树已经大大降低了。
范围查找时,能通过叶子节点的指针获取数据。例如查找大于等于3的数据,当在叶子节点中查到3时,通过3的尾指针便能获取所有数据,而不需要再像二叉树一样再获取到3的父节点。

总结:

1)二叉查找树(BST):解决了 排序 的基本问题,但是由于无法保证平衡,可能退化为链表

2)平衡二叉树(AVⅥL):通过旋转解决了平衡的问题,但是旋转操作效率太低

3)红黑树:通过舍弃严格的平衡和引入红黑节点,解决了AⅥ旋转效率过低的问题,但是在磁盘等场景下,树仍然太高,IO次数太多

4)B树:通过将二叉树改为多路平衡查找树,解决了树过高的问题

5)B+树:在B树的基础上,将非叶节点改造为不存储数据的纯索引节点,进一步降低了树的高度;此外将叶节点使用指针连接成链表,范围查询更加高效。

仅做学习使用,权侵删,禁止转发

https://www.cnblogs.com/tongo...

https://www.bilibili.com/read...

http://www.coder55.com/questi...

有疑问加站长微信联系

MySQL的索引,为什么是B+而不是平衡二叉树

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

算法帝国

算法帝国

克里斯托弗•斯坦纳 / 李筱莹 / 人民邮电出版社 / 2014-6 / 49.00

人类正在步入与机器共存的科幻世界?看《纽约时报》畅销书作者讲述算法和机器学习技术如何悄然接管人类社会,带我们走进一个算法统治的世界。 今天,算法涉足的领域已经远远超出了其创造者的预期。特别是进入信息时代以后,算法的应用涵盖金融、医疗、法律、体育、娱乐、外交、文化、国家安全等诸多方面,显现出源于人类而又超乎人类的强大威力。本书是《纽约时报》畅销书作者的又一力作,通过一个又一个引人入胜的故事,向......一起来看看 《算法帝国》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

MD5 加密
MD5 加密

MD5 加密工具