前言
B+树,是数据库索引的一个数据类型。B+树,是从最早的平衡二叉树演化而来。先了解一下二叉查找树、平衡二叉树、和B树。
二叉查找树
左子树的键值小于根的键值,右子树的键值大于根的键值。
二叉查找树可以任意地构造,以下这种也是二叉查找树,但是其查询效率太低
平衡二叉树
平衡二叉树(AVL树)在符合二叉查找树的条件下,还满足任何节点的两个子树的高度最大差为1。
当失去平衡时,有四种姿态:
- “左左”。插入或删除一个节点后,根节点的左孩子(Left Child)的左孩子(Left Child)还有非空节点,导致根节点的左子树高度比右子树高度高2,AVL树失去平衡。
- 将根节点的左孩子作为新根节点。
- 将新根节点的右孩子作为原根节点的左孩子。
- 将原根节点作为新根节点的右孩子。
- “右右”。插入或删除一个节点后,根节点的右孩子(Right Child)的右孩子(Right Child)还有非空节点,导致根节点的右子树高度比左子树高度高2,AVL树失去平衡。
- 将根节点的右孩子作为新根节点。
- 将新根节点的左孩子作为原根节点的右孩子。
- 将原根节点作为新根节点的左孩子。
- “左右”。插入或删除一个节点后,根节点的左孩子(Left Child)的右孩子(Right Child)还有非空节点,导致根节点的左子树高度比右子树高度高2,AVL树失去平衡。
- 围绕根节点的左孩子进行RR旋转。
- 围绕根节点进行LL旋转。
- “右左”。插入或删除一个节点后,根节点的右孩子(Right Child)的左孩子(Left Child)还有非空节点,导致根节点的右子树高度比左子树高度高2,AVL树失去平衡。
- 围绕根节点的右孩子进行LL旋转。
- 围绕根节点进行RR旋转。
B Tree
满足的条件
- 树中每个结点至多有m个孩子;
- 除根结点和叶子结点外,其它每个结点至少有m/2个孩子;
- 若根结点不是叶子结点,则至少有2个孩子;
- 所有叶子结点(失败节点)都出现在同一层,叶子结点不包含任何关键字信息;
- 所有非终端结点中包含下列信息数据 ( n, A0 , K1 , A1 , K2 , A2 , … , Kn , An ),其中: Ki (i=1,…,n)为关键字,且Ki < Ki+1 , Ai (i=0,…,n)为指向子树根结点的指针, n为关键字的个数
- 非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;
特征
- 关键字集合分布在整颗树中;
- 任何一个关键字出现且只出现在一个结点中;
- 搜索有可能在非叶子结点结束;
- 其搜索性能等价于在关键字全集内做一次二分查找;
- 自动层次控制;
B+Tree
满足条件
- 树中每个非叶结点最多有 m 棵子树;
- 根结点 (非叶结点) 至少有 2 棵子树。除根结点外, 其它的非叶结点至少有 ém/2ù 棵子树;有 n 棵子树的非叶结点有 n-1 个关键码。
- 所有叶结点都处于同一层次上,包含了全部关键码及指向相应数据对象存放地址的指针,且叶结点本身按关键码从小到大顺序链接;
- 每个叶结点中的子树棵数 n 可以多于 m,可以少于 m,视关键码字节数及对象地址指针字节数而定。
- 若设结点可容纳最大关键码数为 m1,则指向对象的地址指针也有 m1 个。
- 结点中的子树棵数 n 应满足 n 属于[m1/2, m1]
- 若根结点同时又是叶结点,则结点格式同叶结点。
- 所有的非叶结点可以看成是索引部分,结点中关键码 Ki 与指向子树的指针 Pi 构成对子树 (即下一层索引块) 的索引项 ( Ki, Pi ),Ki 是子树中最小的关键码。
- 特别地,子树指针 P0 所指子树上所有关键码均小于 K1。结点格式同B树。
- 叶结点中存放的是对实际数据对象的索引。
- 在B+树中有两个头指针:一个指向B+树的根结点,一个指向关键码最小的叶结点。
特性
- 所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;
- 不可能在非叶子结点命中;
- 非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层;
- 更适合文件索引系统
保持树平衡主要是为了提高查询性能,但为了维护树的平衡,成本也是巨大的,当有数据插入或删除时,需采用拆分节点、左旋、右旋等方法。B+树因为其高扇出性,所以具有高平衡性,通常其高度都在2~3层,查询时可以有效减少IO次数。B+树索引可以分为聚集索引(clustered index)和非聚集索引(即辅助索引,secondary index)。
- 聚集索引:InnoDB表时索引组织表,即表中数据按主键B+树存放,叶子节点直接存放数据,每张表只能有一个聚集索引。
-
辅助索引:辅助索引(也称非聚集索引)是指叶节点不包含行的全部数据,叶节点除了包含键值之外,还包含一个书签连接,通过该书签再去找相应的行数据。
B-Tree、B+-Tree、Skip-List, 都在用了二分查找的思想
参考:
http://www.cburch.com/cs/340/reading/btree/index.html
https://www.cnblogs.com/wade-luffy/p/6292784.html
http://blog.codinglabs.org/articles/theory-of-mysql-index.html
https://www.cnblogs.com/vianzhang/p/7922426.html
https://www.cnblogs.com/gym333/p/6877023.html
https://www.cs.helsinki.fi/u/mluukkai/tirak2010/B-tree.pdf
http://itindex.net/detail/44489-mysql-%E7%B4%A2%E5%BC%95