b+tree

为什么用 b+ 树而不是 b 树？

B+树是B树的改进，简单地说是：只有叶子节点才存数据，非叶子节点是存储的指针；所有叶子节点构成一个有序链表

B+树非叶子节点不存在数据只存索引，B树非叶子节点存储数据。

B+树查询效率更高。B+树使用双向链表串连所有叶子节点，区间查询效率更高（因为所有数据都在B+树的叶子节点，扫描数据库只需扫一遍叶子结点就行了），但是B树则需要通过中序遍历才能完成查询范围的查找。

B+树查询效率更稳定。B+树每次都必须查询到叶子节点才能找到数据，而B树查询的数据可能不在叶子节点，也可能在，这样就会造成查询的效率的不稳定

B+树的磁盘读写代价更小。

O(logN)