B树和B+树的区别。

提示

题眼： 自平衡多叉树，叶子节点链表相连，MySQL的进一步优化。

B树和B+树都是一种自平衡的多叉树，它们有以下区别：

1. 数据存放位置不同：
   B树：B树的叶子节点和非叶子节点都可以存放数据。每个节点存的是数据和指针。
   B+树：B+树的所有数据都存放在叶子节点上，非叶子节点存放的是索引。
2. B+树更适合范围查询：
   B+树的叶子节点是一个有序链表，B树的叶子节点是无序的。所以B+树更适合范围查询。
3. .MySQL对B+树有优化：
   经过MySQL的优化B+树的叶子节点上存的是数据页，数据页上面缀的是有序链表，数据页之间使用双向指针连接。每个数据页不超过16kb的数据。

重要

参考答案：

B树和B+树都是一种自平衡的多叉树，他们在数据组织上都是一种矮胖矮胖的结构，一般MySQL里的B+树也就3-4层左右，这样的好处是树高较低，需要的IO次数较少。他们两个最主要的区别是叶子节点的数据组织形式，B树的叶子节点上存放的数据是零散的，而B+ 树叶子节点之间又通过指针的方式相连，这样可以方便的进行范围查询。另外，B树的非叶子节点也会存放数据，而B+树非叶子节点只存放索引，所有的数据都在叶子节点上。除此以外，MySQL对B+树还有一些优化，它的叶子节点上存的不是一个单的数据，而是一个数据页，数据页里能存放多条数据，每个数据页默认16Kb大小，数据页的头部会有指针相连。

todo