B+树

视频

印度老哥

视频笔记

1.1 block

disk 的最小单位 block，block 的 address number 可被唯一的 track number、sector number 确定。 01:36

1.2 主存和 disk

05:53 disk 不能直接处理数据，需要将数据传入主存，在主存中对数据进行操作，再返回数据。 主存中的数据：数据结构（datastructure） disk 中的数据：DBMS（database management system）

1.3 寻找特点数据的时间/Index

08:53 ==因为每个 block 存放的地址不确定，所以要查找特定的==

• 先确定 block 基本大小 （多少bites）
• 根据 row 的 bites 计算每个 block 能存放多少 rows
• 用 index 存放关键信息，计算一个 block 能存多少index
• 根据所需 index 个数判断需要的高级索引表个数
• 所需时间：最高级索引表 block 个数+剩余索引表个数（比如，我现在有 100 个 row、两级 index，高级 index 有 3 个 block，那么我需要查询的 block 数：3+1+1） （index 一般只包含关键信息和所在行的 pointer）

1.4 树、B+树

1. M-way 树 （degree：M）
   1. 18:48
   2. 每个 node 至多有 m-1 个 key，至少有 [m/2]-1 个 key (except root node)，至多 m 个 children，至少 [m/2] 个 children
   3. node 结构（以 4-way 树举例）：【pointer 1】【k 1】【record pointer 1】【pointer 2】【k 2】【rp 2】【pointer 3】【k 3】【rp 3】【pointer 4】 每个 child pointer 有一个 record pointer
   4. 问题：过久的搜索时间
2. B 树 (自下而上生长)
   1. 27:50
   2. [m/2]个 children
   3. 根 最少有两个 children
   4. 所有的 leaf 在 same level
   5. 举例： → → → →
3. B+ 树
   1. 37:13
   2. 并非所有 child pointer 都有 record pointer，只有 leaf node 的 child pointer 有 record pointer.
   3. 所有的 key 在 leaf code 都有一个 copy.
   4. 所有的 leaf form a linked list
   5. B+树比起 B 树，更像多级索引表
   6. leaf 是第一级 index ,再往上是第二级 index,以此类推。

B+树 insertions

B+Tree Insertions - YouTube

rules

1. First, give to left
2. Second, give to right
3. If above no work, split the node, elements should be more in the new node
4. If split, you will create a father node, and parent node save the lowest value of every child expect the first child

B+ tree deletionsB+Tree Deletions - YouTube

1.