B+树

说起B+树，在数据库领域大名鼎鼎，大多数的数据库厂家都用B+树来组织索引。这其实都是基于一个朴素的想法：减少IO读取的次数，尽快找到需要的数据。为什么不用二叉树？因为当数据很多的时候，二叉树的层数太多，每层就代表了一次的IO，明显不合适。为什么不用B树？B树可是有m分叉的，先看一下B树的样子 再看一下B+树的样子 相比B树，B+树的中间节点不用保存数据， 因为在叶子节点上保存了所有的元素，这个特点特别重要，意味着一个中间节点(non leaf) page能够容纳更多节点元素，这样在IO读取的时候，不用读很多页。对于范围查找来说，B+树只需遍历 叶子节点链表即可，b树却需要重复地中序遍历。 以下两个链接方便比较B树和B+树的区别 https://www.cs.usfca.edu/~galles/visualization/BTree.html https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html