MySQL索引底层

包含n(n为整数，大于0)个结点， n-1条边的有穷集，它有以下特点：

• 每个结点或者无子结点或者只有有限个子结点;
• 有一个特殊的结点,它没有父结点，称为根结点;
• 每一个非根节点有且只有一个父节点;
• 树里面没有环路

一些有关于树的概念：

• 结点的度：一个结点含有的子结点个数称为该结点的度;
• 树的度：一棵树中，最大结点的度称为树的度;
• 父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点;
• 深度：对于任意结点n,n的深度为从根到n的唯一路径长，根结点的深度为0;
• 高度：对于任意结点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0;

树的种类序性，可以分为有序树和无序树：

• 无序树：树中任意节点的子结点之间没有顺序关系
• 有序树：树中任意节点的子结点之间有顺序关系

按照节点包含子树个数，可以分为B树和二叉树，二叉树可以分为以下几种：

• 二叉树：每个节点最多含有两个子树的树称为二叉树;
• 二叉查找树：首先它是一颗二叉树，若左子树不空，则左子树上所有结点的值均小于它的根结点的值;若右子树不空，则右子树上所有结点的值均大于它的根结点的值;左、右子树也分别为二叉排序树;
• 满二叉树：叶节点除外的所有节点均含有两个子树的树被称为满二叉树;
• 完全二叉树：如果一颗二叉树除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布
• 霍夫曼树：带权路径最短的二叉树。
• 红黑树：红黑树是一颗特殊的二叉查找树，每个节点都是黑色或者红色，根节点、叶子节点是黑色。如果一个节点是红色的，则它的子节点必须是黑色的。
• 平衡二叉树(AVL)：一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

B-树、B+树简介

B-树简介

B-树，也称为B树，是一种平衡的多叉树(可以对比一下平衡二叉查找树)，它比较适用于对外查找。看下这几个概念哈：

• 阶数：一个节点最多有多少个孩子节点。(一般用字母m表示)
• 关键字：节点上的数值就是关键字
• 度：一个节点拥有的子节点的数量。

一颗m阶的B-树，有以下特征：

• 根结点至少有两个子女;
• 每个非根节点所包含的关键字个数 j 满足：⌈m/2⌉ - 1 <= j <= m - 1.(⌈⌉表示向上取整)
• 有k个关键字(关键字按递增次序排列)的非叶结点恰好有k+1个孩子。
• 所有的叶子结点都位于同一层。

一棵简单的B-树如下：

（编辑：江门站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!