B+树的常识
首先我们来介绍一下B+树。B+树是一种平衡树，而与普通的树不同的是：
- B+树的叶子节点包含所有数据，并且叶子节点有序的用双向循环链表进行连接，因此可以实现从根节点读，也可以从叶子节点遍历。
- B+树的每个非叶子节点有n棵子树则有n个关键字（不同于B树的靠关键字之间的缝隙来定义指针，而直接由关键字定义指针）
- 所有非终端节点可以看成是索引部分，节点中仅含有其子树根节点最大（或最小）关键字
那么B+树的优势也就可以看出来了： - B+树中非叶子节点并不包含指向竿见自具体信息的指针，因此内部节点比B树更小，因此一次性读入内存更多的关键字，IO的读写次数也就降低了。
- 查询效率稳定，因为对于每一次查询，都需要从根节点走到叶子节点才能拿到具体指向文件的信息，所以关键字查询的路径长度相同。
- B+树方便扫库，从叶子节点扫一遍就行，不用采用中序遍历之类的
- B+树支持range-query非常方便，这是主要原因。（举个例子：要查5-10之间数据，第一次查5.再一次查10，然后串起来遍历就行，而B树就很麻烦了）
B+树的劣势在于树的高度会比B树高一些，对于频率查询B树也更好，因为可以将频率高的节点上升。
Read full article from MySQL-InnoDB索引与算法 | 天遥的码农日常
No comments:
Post a Comment