平衡二叉树
- 非叶子节点最多拥有两个子节点；
- 非叶子节值大于左边子节点、小于右边子节点；
- 树的左右两边的层级数相差不会大于1;
- 没有值相等重复的节点
- 平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构
- 平衡二叉树是采用二分法思维把数据按规则组装成一个树形结构的数据，用这个树形结构的数据减少无关数据的检索，大大的提升了数据检索的速度
B树
- 描述B树时，需要指定它的阶数，M阶树表明一个节点最多有M-1个关键字，M个子节点
- 也称B-树,它是一颗多路平衡查找树
- 每个节点最多有m-1个关键字
- 根节点最少可以只有1个关键字，1 <= k <= m-1
- 非根节点至少有m/2个关键字， m/2 <= k <= m-1
- 每个节点有M-1个key，并且以升序排列
- 每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它
- 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同
- 每个节点都存有索引和数据，也就是对应的key和value
- 例：5阶的B树，根节点数量范围：1 <= k <= 4，非根节点数量范围：2 <= k <= 4
- 索引查询的数据主要受限于硬盘的I/O速度，查询I/O次数越少，速度越快，B树访问I/O次数比平衡二叉树少，B树做为索引的查询效率高。
B+树
- mysql的底层实现存储结构
- 根节点至少一个元素
- 非根节点元素范围：m/2 <= k <= m-1
- B+树有两种类型的节点：内部结点（也称索引结点）和叶子结点。内部节点就是非叶子节点，内部节点不存储数据，只存储索引，数据都存储在叶子节点。
- B+树是应文件系统所需而产生的B树的变形树
B*树
|