数据库二叉树
❶ 数据库索引为什么使用B+树
B tree： 二叉树（Binary tree），每个节点只能存储一个数。
B-tree： B树（B-Tree，并不是B“减”树，横杠为连接符，容易被误导）
B树属于多叉树又名平衡多路查找树。每个节点可以多个数（由磁盘大小决定）。
B+tree 和 B*tree 都是 B-tree的变种
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。而B-/+/*Tree，经过改进可以有效的利用系统对磁盘的块读取特性，在读取相同磁盘块的同时，尽可能多的加载索引数据，来提高索引命中效率，从而达到减少磁盘IO的读取次数。
不了解磁盘相关知识的可以查看 硬盘基本知识（磁头、磁道、扇区、柱面）
下面通过示意图来看一下，B-tree、B+tree、B*tree
从图中可以看出，B-tree 利用了磁盘块的特性进行构建的树。每个磁盘块一个节点，每个节点包含了很关键字。把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度。
B-tree巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页（每页为4K），这样每个节点只需要一次I/O就可以完全载入。
B-tree 的数据可以存在任何节点中。
B+tree 是 B-tree 的变种，数据只能存储在叶子节点。
B+tree 是 B-tree 的变种，B+tree 数据只存储在叶子节点中。这样在B树的基础上每个节点存储的关键字数更多，树的层级更少所以查询数据更快，所有指关键字指针都存在叶子节点，所以每次查找的次数都相同所以查询速度更稳定;
B*tree 每个磁盘块中又添加了对下一个磁盘块的引用。这样可以在当前磁盘块满时，不用扩容直接存储到下一个临近磁盘块中。当两个邻近的磁盘块都满时，这两个磁盘块各分出1/3的数据重新分配一个磁盘块，这样这三个磁盘块的数据都为2/3。
在B+树的基础上因其初始化的容量变大，使得节点空间使用率更高，而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少；
❷ 深入理解(二叉树、平衡二叉树、B-Tree、B+Tree )的区别
二叉树、平衡二叉树、BTree、B+Tree的主要区别如下：
1. 二叉查找树： 基础结构：通过二分查找法提升数据查找速度，每个节点存储一个键值和数据，每个节点最多有两个子节点。 缺点：当树结构不平衡时，查询效率会显着降低。
2. 平衡二叉树： 特点：确保树的高度平衡，从而保持稳定的查找效率。 节点存储：每个节点存储单一键值和数据。 子节点数量：每个节点最多有两个子节点。 优势：通过旋转操作保持高度平衡，提高查找效率。
3. BTree： 节点存储：节点能存储多个键值和数据，每个节点有多于两个的子节点。 适用场景：适合海量数据存储，通过增加节点中键值的数量来减少树的高度，从而减少磁盘I/O操作。 优点：在大量数据存取时，能显着提高查找、插入和删除操作的效率。
4. B+Tree： 节点结构：非叶子节点仅存储指针，叶子节点保存所有数据和指针。 查询稳定性：由于所有实际数据都存储在叶子节点，且叶子节点之间通过指针相连，使得查询更加稳定。 排序性能：叶子节点形成了一个有序的链表，非常适合范围查找和排序操作。 应用场景：在MySQL的InnoDB存储引擎中，B+Tree常用于聚集索引，以提高查询效率。
总结： 二叉查找树是基础数据结构，但在不平衡时效率较低。 平衡二叉树通过保持高度平衡来提高查找效率。 BTree通过增加节点中键值的数量来优化存储效率和磁盘访问。 B+Tree在BTree的基础上进一步改进，提高了查询稳定性和排序性能，特别适用于数据库索引等场景。
❸ C语言 什么叫完全二叉树
完全二叉树是一种特殊的二叉树。
定义：如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。
例：
特点：
叶子结点只可能在最大的两层上出现,对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L 或 L+1。
完全二叉树第i层至多有2^（i-1）个节点，共i层的完全二叉树最多有2^i-1个节点。
满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。