数据库？为什么数据库要用B+树？说到前言中的索引，第一反应肯定是它可以提高查询效率。比如一本书的目录，如果要找某个章节，首先会从目录中定位。如果您没有目录，则必须翻遍所有内容才能找到它。索引的设计对程序的性能至关重要。索引太少会影响查询性能；如果索引过多，会影响增加/修改/删除的性能。知识点MySQL一般支持以下几种常见的索引：B+树索引全文索引hash索引今天我们将重点介绍B+树索引以及为什么使用B+树作为索引数据结构。B+树索引不能直接找到具体的行，只能找到查找到的行所在的页，然后DB将整个页读入内存，然后在内存中查找。1、与二叉树相比，二叉树相对于顺序搜索确实减少了搜索次数，但是在最坏的情况下，二叉树可能会退化为顺序搜索。而且就二叉树本身而言，当数据库的数据量特别大的时候，层数也会特别多。二叉树的高度一般是log_2^n，B树的高度是log_t^((n+1)/2)+1，比B树大lgt倍左右。n是节点总数，t是树的最小度数。2、与B-tree相比，B-tree在提升IO性能的同时，并没有解决遍历元素时效率低下的问题。B+号就是为了解决这个问题而应运而生的。B+数只需要遍历叶子节点即可实现整棵树的遍历，而B-树则必须使用中序遍历，按顺序扫描库。B+树非常方便地支持范围查询。这也是数据库选择B+树的主要原因。另外，最后，并不是说B+树就比B树好。有许多使用B树的基于频率的搜索。查询节点越频繁，越到根。进行一些更改的关键。不管是B-tree还是B+树，由于前面层层的反复查询，已经加载到内存中了，不会有磁盘读IO。一般在开机的时候会主动swap到内存中。B+树在内存中没有优势，只有在磁盘中B+树的威力才能显现出来。使用B+树的索引结构的优点：B+树的高度一般为2-4层，所以查找记录时最多只需要2-4次IO，相比二叉树有了很大的降低平衡树。范围搜索时，可以通过叶子节点的指针获取数据。比如查找大于等于3的数据，当在叶子节点中找到3时，可以通过3的尾指针获取所有数据，而不需要像二叉树那样获取3的父节点。总结：1）二叉搜索树（BST）：解决了排序的基本问题，但是由于不能保证平衡，可能会退化为链表2）平衡二叉树（AVVIL）：通过轮换解决平衡问题，但是旋转操作效率太低3）红黑树：通过放弃严格平衡，引入红黑节点，解决了AVI旋转效率低的问题，但是在磁盘等场景下，树还是太高了IO数过高4）B树：通过将二叉树改为多路平衡搜索树，解决树过高问题5）B+树：在B树的基础上，对非-叶子节点变成不存储数据的纯索引节点，进一步降低了树的高度；另外，叶子节点使用指针连接成链表，范围查询效率更高。仅供学习使用，侵权删帖，禁止转发参考：https://blog.csdn.net/qq_3803...https://www.cnblogs.com/tongo...https://www.bilibili。com/read...http://www.coder55.com/questi...
