MySQL为什么使用B+树

在线查看数据格式链接:Data Structure Visualization https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

 常见数据结构:

        1.数组:数组是内存中一块连续的内存空间，定义一个数组对象，就需要先指定数组的大小,当存储数据的大小大于定义的数组大小,就需要对数组进行扩容(定义一个更大的数据),并将原本数组的数据复制到新数组中,这样性能消耗会比较大。

        2.链表:链表是一种线性数据结构，它由一系列节点组成，这些节点在物理上可以是连续的也可以是不连续的，它们通过指针连接在一起。当需要查找数据的时候会从头部开始遍历,时间复杂度为O(n)。

        3.二叉查找树:二叉查找树左子树上节点值小于根节点的值，右子树上节点值大于根节点的值。当需要快速查找时，将数据存储在BST是一种常见的选择，因为此时查询时间取决于树高，平均时间复杂度是O(lgn)。然而，BST可能长歪而变得不平衡，如下图所示，此时二叉树退化为链表，时间复杂度退化为O(n)。

        4.红黑树:红黑树虽然实现了平衡节点，但是每个节点只能存储一个元素的结构还是会导致树高度很高，不如B树和B+树的索引文件页的方式存储。

        5.B树:B树是为磁盘等辅存设备设计的多路平衡查找树，与二叉树相比，B树的每个非叶节点可以有多个子树。因此，当总节点数量相同时，B树的高度远远小于AVL树和红黑树(B树是一颗“矮胖子”)，磁盘IO次数大大减少。

        6.B+树:

                (1)B树的每个节点都会存储data数据，而B+Tree的话非叶子节点是存储的索引（冗余），不存储data数据，这样每一页文件页能存储的节点就很多，树的高度就可以得到很好的控制，树的高度越高，从磁盘load节点到内存对比的次数就会越多，磁盘I/O是费时。

                (2)所以B+Tree在树高度相同的情况下能够存储更多的索引数据，间接的减少了磁盘的I/O操作，B+Tree的I/O次数会更加稳定一些。

               (3)从范围查询的角度上来说B+Tree也具备绝对的优势，因为B+Tree在每个相邻的叶子节点之间都有互相指向

                (4)B+Tree在全表扫描的情况下也是比较占优势的，因为B+Tree的数据都是存储在非叶子节点的，所以只需要扫描叶子节点就可以拿到全部数据了，B Tree的话就需要从头遍历整颗树。