2017编程提高第9.5节课——BTree和数据库索引
LanyuanXiaoyao's Blog ヽ(✿゚▽゚)ノ

2017编程提高第9.5节课——BTree和数据库索引


回顾一下

二叉查找树

二叉查找树和索引

硬盘

磁头是怎么运动的

读取数据

B-Tree

  • 一个更胖的“二叉查找树”
  • 一个m阶的B-Tree定义:
    • 树中每个结点至多有m棵子树
    • 若根结点不是叶子结点,则至少有两棵子树
    • 除根之外的所有非终端结点至少有ceil(m/2)棵子树
    • 所有的非终端结点中包含下列信息数据 (n, A0, K1, A1, K2, A2, …, Kn, An)     即n个关键字, n+1个指针 Key 是有序的, k1<k2<…Kn

4阶的B-Tree

  1. 树中每个结点至多有4棵子树;
  2. 若根结点不是叶子结点,则至少有两棵子树;
  3. 除根之外的所有非终端结点至少有ceil(m/2) = 2棵子树; 
  4. 所有的非终端结点中包含下列信息数据 (3, A0, K1, A1,K2, A2,K3,A3)   即3个 key , 4个指针(子树) (2, A0, K1, A1,K2, A2,)  即2个 key , 3个指针(子树) (1, A0, K1, A1)  即1个 key , 2个指针(子树)

3阶的B-Tree

  1. 树中每个结点至多有3棵子树;
  2. 若根结点不是叶子结点,则至少有两棵子树;
  3. 除根之外的所有非终端结点至少有ceil(m/2) = 2棵子树; 
  4. 所有的非终端结点中包含下列信息数据 (2, A0, K1, A1,K2, A2,)  即2个 key , 3个指针(子树) (1, A0, K1, A1)  即1个 key , 2个指针(子树)

4阶的B-Tree

B-Tree的查找 (以3-阶为例)

B-Tree的插入 (以3-阶为例)

要插入的数据为30, 26, 85, 7

给30找个位置

下一个等待插入的数字:26

26放到哪儿?

把30 升级到父节点

下一个等待插入的数字:85

85放到哪里?

70升级到父节点,还是不行

终于可以了

下一个等待插入的数字:7

7找到合适的位置,但是再次违反规则

把7提到父节点,仍然不行

把24提到根节点

再次分裂, 树增加了一层

思考一下

  • 节点在不断地“分裂”,将一个Key送到父节点
  • “分裂”是局部的, 只影响相关的节点和链接。
  • “分裂”不会影响全局有序性和平衡性: 任意空链接到根节点的路径长度都是相等的。
  • 只有当根节点分裂时, 树的高度才会增加。

3阶B-Tree删除

删除12后的B-Tree

接下来要删除的数字:50

删除50

如果想删除53,该怎么处理

53被删除

如果想删除37 呢?

还需要继续处理原来的24节点

如何把45删除

B+ Tree

  • B+ Tree是应文件系统需求所产生一个一种B Tree的变种, 一颗m阶的B+Tree和m阶的B-Tree ,主要差别在于:
  • –有n棵子树的节点有n个key (而不是n-1个)
  • 所有叶子节点包含了全部的key, 以及指向相关记录的指针。叶子节点本身也会依照key自小而大链接起来
  • 所有中间节点都可以看做是索引部分,节点中仅仅含有子树的最小/最大的key, 但是不再保存数据

B+ Tree索引

B+ Tree的优势

  • 节点可以存放更多的key
    • 因为key 对于的数据地址只存放在叶子节点
  • 查询一个范围内的数据更有效
    • Age > =51 and age <=91

Backup

Mysql Innodb


相似文章

评论