B+树原理了解

前言

B+树,是数据库索引的一个数据类型。B+树,是从最早的平衡二叉树演化而来。先了解一下二叉查找树、平衡二叉树、和B树。

二叉查找树

左子树的键值小于根的键值,右子树的键值大于根的键值。

二叉查找树-0

二叉查找树可以任意地构造,以下这种也是二叉查找树,但是其查询效率太低

二叉查找树-0

平衡二叉树

平衡二叉树(AVL树)在符合二叉查找树的条件下,还满足任何节点的两个子树的高度最大差为1。

AVL Tree

当失去平衡时,有四种姿态:

  • “左左”。插入或删除一个节点后,根节点的左孩子(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

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

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

发表评论

This site uses Akismet to reduce spam. Learn how your comment data is processed.