平衡二叉树

• 平衡二叉树又被称为AVL树
• 
• 平衡二叉树是一颗空树或者它的左右两个子树的高度差的绝对值不超过1，并且左右子树也是平衡树
• 非叶子节点值大于左子节点值而小于右子节点值
• 非叶子节点最多拥有两个子节点

• 平衡二叉树的不足之处及时间复杂度

• 如果每次插入的数据都比上一次插入的数据大，那么用平衡二叉树就会以线性方式进行存储，所以他的时间复杂度为O(n)。在mysql中一张表存储百万条数据是很正常的一件事，这样会导致树的深度更深，导致大量的IO操作。还有就是mysql进行过磁盘读取时，是以页为单位进行读取，每个节点表示一页。而平衡二叉树每个节点存储一个关键词，导致存储空间被浪费。

• 红黑树

• 每个节点要么是红色要么是黑色
• 根节点是黑色
• 每个叶子节点(NIL)是黑色
• 每个红色节点的两个子节点一定为黑色
• 任意一个节点到每个叶子节点的路径都包含数量相同的黑色节点
• 如果一个节点存在黑子节点，那么该节点肯定有两个子节点
• 

• B-树

   B-树（B树）并不只能有三层。B树的高度取决于其阶数（即每个节点最多可以拥有的子节点数）以及树中存储的元素数量。
• 每个节点中，都包含数据(key和data域)和指针，相互间隔
• 叶节点具有相同的深度，叶节点的指针为空
• 节点中的数据索引从左到右递增排列
• 所有索引元素不重复
• 

  B-树相比平衡二叉树优点

• 每个节点存储多个多个关键词，合理利用空间大小，每次mysql进行读取时，都会进行预读取，每次把该节点数据读取出来并存储到内存中
• B-树中每个节点存储的关键词变多，导致存储相同数量的数据，B-树的深度相比平衡二叉树深度更浅，减少了数据的查找次数和复杂度

• B+树

  B+树同样也不只能有三层，从罕见角度来说他也可以一层，二层，但是很罕见
• 非叶子节点中不存储data，只存储索引，可以放更多的索引
• 叶子节点包含所有索引字段
• 叶子节点包含数据(key和data域)和指针
• 叶子节点用指针连接，提高区间访问的性能
• 

• B+树对比红黑树

• 红黑树多用于内部排序，即全放在内存中
• B+树多用于外存上时，B+也被成为一个磁盘友好的数据结构
• 红黑树和平衡二叉树有相同缺点，每个节点存储一个关键词，数据量大时，导致红黑树的深度很深，mysql每次读取时消耗大量io

B+树通常设计为三层的原因主要包括以下几点‌：

一个高度为3的B+树大概可以存放：1170*1170*16=21902400行数据。
所以在InnoDB中B+树高度一般为1-3层，它就能满足千万级的数据存储。
在查找数据时一次页的查找代表一次IO，所以通过主键索引查询通常只需要1-3次逻辑IO操作即可查找到数据。
‌性能优化‌：三层B+树可以在保证性能的同时，减少对磁盘的I/O操作。例如，一个三层B+树在查找数据时，最多只需要三次I/O操作，这大大提高了数据查找的效率‌1。
‌存储效率‌：三层B+树可以存储大量的数据。假设每个节点存储16KB的数据，一个三层B+树可以存储大约2000万条数据，这足以满足大多数应用场景的需求‌2。
‌平衡性‌：B+树的插入和删除操作会保持树的平衡，三层结构可以确保树的深度适中，避免过深的树结构导致的性能下降‌2。
‌维护成本‌：三层结构相对简单，维护成本较低。过多的层数会增加树的复杂度，从而增加维护和管理的难度‌2。
‌实际应用场景‌：在实际应用中，三层B+树已经能够满足大多数数据库和文件系统的需求，不需要更深层次的树结构‌2。

B+树的时间复杂度是多少？

由于B+树所有的 data 域都在根节点，所以查询 key 的节点必须从根节点索引到叶节点，时间复杂度固定为 O(log n)。

B+树相比B-树的优点

B+树非叶子节点只存储key值，而B-树存储key值和data值，这样B+树每次读取时可以读取到更多的key值
mysql进行区间访问时，由于B+树叶子节点之间用指针相连，只需要遍历所有的叶子节点即可；而B-树则需要中序遍历那样遍历
B+树非叶子节点只存储key值，而B-树存储key值和data值，导致B+树的层级更少，查询效率更高
B+树所有关键词地址都存在叶子节点上，所以每次查询次数都相同，比B-树稳定

为什么高度为3的B+树存储千万级数据？

解释这个问题的前提，mysql使用InnoDB引擎，mysql默认页文件大小为16k
假设我们一行数据大小为1k，那么一页存储16条数据，也就是说一个叶子节点能存储16条数据
再来看看非叶子节点，假设主键ID为bigint类型，那么长度为8B，指针大小在InnoDB引擎中的大小为6B，一共14B，那么一页中可以存放16k/14B=1170个(主键+指针)
也就是说高度为2的B+树可以存储的数据为:1170*16=18720条；高度为3的B+树可以存储的数据为:11701170*16=21902400(千万条数据)