树

定义

• 树是一种非线性的数据结构
• 树是若干个结点的集合(个数>=0),是由唯一的根和若干棵互不相交的子树组成
• 树的结点树可以为0，对于这种树，我们称为空树
• 树与图的区别在于树中没有一个闭环

基本术语

• 结点：组成树的元素，结点包含数据元素和指向子树的分支
• 结点的度：结点分支数
• 树的度：结点拥有的最大分支数
• 叶子结点：度为0的结点

二叉树

定义：即每个结点都最多只有两个子结点的树

完全二叉树

高度为h的二叉树，其1~h-1层为满结点，且其h层（叶子结点层）的节点从左至右依次排列（最多2^h-1个，最少1个）

满二叉树

除最后一层外，每个结点都有左右子结点的二叉树

平衡二叉树

任一结点的左右子树的高度差绝对值不超过1，且左右子树均为平衡二叉树（防止树退化成链表）

二叉排序树（二叉查找树）

左小右大，子树也是二叉查找树

删除与插入操作

平衡二叉树

左右子树的深度之差绝对值不超过1；子树都是平衡二叉树

B树

概念： 1. B树每个节点有K（K>0）个关键字（根节点除外，根节点没有关键字时树为空），结点的分支数等于关键字数+1，最大的分支数就是B树的阶数，因此m阶的B树中结点最多有m个分支 非根节点和叶子节点的其他节点，分支数 > (阶数 / 2)，若5阶B树则非叶子节点分支数至少为3 结点内各关键字互不相等且按从小到大排列，下层节点内的关键字取值总是落在由上层节点关键字所划分的区间内 对于一个m阶B树，关键字个数范围 ceil(m/2) - 1 ~ m -1 (5阶 则是 2 ~ 4)

删除与插入操作

B+Tree

B+树是B树的升级版本,就目前情况，绝大部分都已经用B+树代替了B树了，文件管理、索引等等，当然，具体为什么可以看下面的优点介绍 区别：B+树非叶子节点不存储数据，每个叶子节点指向相邻的叶子节点

查找插入删除与B树类似 但 B+树提供了旋转功能，来尽可能的减少页的拆分 旋转发生在leaf Page已经满了、但是其左右兄弟节点没有满的情况下 B树与B+树的比较 B树中关键字集合分布在整棵树中，叶节点中不包含任何关键字信息，而B+树关键字集合分布在叶子结点中，非叶节点只是叶子结点中关键字的索引； B树中任何一个关键字只出现在一个结点中，而B+树中的关键字必须出现在叶节点中，也可能在非叶结点中重复出现；

原文：https://blog.csdn.net/qq_34694342/article/details/84255739