MySQL为什么要使用b+树

一、b+树结构

查询5的过程：从顶层开始5小于7找到页号6，5大于4，找到页号105，然后二分查找找到5.

二、为什么不用二叉树

理想的平衡二叉树查询效率是O（logN），但是极端情况下二叉树可能会退化成链表，查询效率降为O（n）

三、为什么不使用红黑树

与AVL树相比，红黑树并不追求严格的平衡，而是大致的平衡：只是确保任一结点左右子树的高度相差不超过两倍。

四、为什么不使用B树

• B树在叶子节点和非叶子节点都存储数据，查询效率不稳定。
• B+树叶子节点所有双向链表链接起来的，适合范围查询。
• B+树的磁盘读写代价更小。B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，通常B+树矮更胖，高度小查询产生的I/O更少。

五、为什么使用B+树

• 1.B+树是多叉树结构，每个结点都是一个16k的数据页，能存放较多索引信息，所以扇出很高。三层左右就可以存储2kw左右的数据。也就是说查询一次数据，如果这些数据页都在磁盘里，那么最多需要查询三次磁盘IO。
• 2.B+树高度较低，磁盘IO次数更少。
• 3.支持范围查询。
• 4.查询效率稳定。