MySQL为啥不用平衡二叉树_MySQL的索引，为什么是B+而不是平衡二叉树

数据库为什么使用B&＃43;树&＃xff1f;

前言

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

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

知识点

MySQL中一般支持以下几种常见的索引&＃xff1a;B&＃43;树索引

全文索引

哈希索引

我们今天重点来讲下B&＃43;树索引&＃xff0c;以及为什么要用B&＃43;树来作为索引的数据结构。

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

1. 与二叉树相比

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

2. 与B树相比

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

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

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

采用B&＃43;树的索引结构优点&＃xff1a;B&＃43;树的高度一般为2-4层&＃xff0c;所以查找记录时最多只需要2-4次IO&＃xff0c;相对二叉平衡树已经大大降低了。

范围查找时&＃xff0c;能通过叶子节点的指针获取数据。例如查找大于等于3的数据&＃xff0c;当在叶子节点中查到3时&＃xff0c;通过3的尾指针便能获取所有数据&＃xff0c;而不需要再像二叉树一样再获取到3的父节点。

总结&＃xff1a;

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

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

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

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

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

仅做学习使用&＃xff0c;权侵删&＃xff0c;禁止转发