B+树的插入和删除策略.[急]

b+树算法：从磁盘读取数据文件，可以进行插入，删除 *** 作，两种方式打印出元素信息。树型打印和依关键字大小打印。-b

tree

algorithm

:

from

disk

to

read

data

files

that

can

be

inserted,

deleted

operation,

print

out

both

elements

of

information.

tree-print

and

print

size

according

to

the

keyword.

我用例子说明算法吧.(假设你懂得B+树的定义)

[插入算法] 假设有一棵3阶B+树

[59 97]

/\

[15 44 59] [72 97]

/ | \ / \

[10 15] [21 37 44] [51 59] [63 72] [85 91 97]

Eg.1 插入9,首先查找9应插入的叶节点(最左下角的那一个),插入发现没有破坏B+树的性质,完毕

[59 97]

/\

[15 44 59] [72 97]

/ | \ / \

[9 10 15] [21 37 44] [51 59] [63 72] [85 91 97]

Eg.2 插入20,首先查找20应插入的叶节点(第二个叶子节点),插入

[59 97]

/\

[15 44 59] [72 97]

/ | \ / \

[10 15] [20 21 37 44] [51 59] [63 72] [85 91 97]

发现第二个叶子节点已经破坏了B+树的性质,则把之分解成[20 21], [37 44]两个,并把21往父节点移

[59 97]

/ \

[15 21 44 59] [72 97]

/ ||\ / \

[10 15] [20 21] [37 44] [51 59] [63 72] [85 91 97]

发现父节点也破坏了B+树的性质,则把之再分解成[15 21], [44 59]两个,并把21往其父节点移

[21 59 97]

/ |\

[15 21] [44 59] [72 97]

/ \ /\ / \

[10 15] [20 21] [37 44] [51 59] [63 72] [85 91 97]

这次没有破坏B+树的性质(如果还是不满足B+树的性质,可以递归上去,直到满足为至),插入完毕

Eg.3 插入100,首先查找100应插入的叶节点(最后一个节点),插入

[59 97]

/\

[15 44 59] [72 97]

/ | \ / \

[10 15] [21 37 44] [51 59] [63 72] [85 91 97 100]

修改其所有父辈节点的键值为100(只有插入比当前树的最大数大的数时要做此步)

[59 100]

/\

[15 44 59] [72 100]

/ | \ / \

[10 15] [21 37 44] [51 59] [63 72] [85 91 97 100]

然后重复Eg.2的方法拆分节点,最后得

[59 100]

/\

[15 44 59] [72 91 100]

/ | \ / |\

[10 15] [21 37 44] [51 59] [63 72] [85 91] [97 100]

[删除算法] 以插入算法的B+树为例

Eg.1 删除91,首先找到91所在叶节点(最后一个节点),删除之

[59 97]

/\

[15 44 59] [72 97]

/ | \ / \

[10 15] [21 37 44] [51 59] [63 72] [85 97]

没有破坏B+树的性质,删除完毕

Eg.2 删除97,首先找到97所在叶节点(最后一个节点),删除之

[59 97]

/\

[15 44 59] [72 97]

/ | \ / \

[10 15] [21 37 44] [51 59] [63 72] [85 91]

修改该节点的父辈的键字为91(只有删除树中最大数时要做此步)

[59 91]

/\

[15 44 59] [72 91]

/ | \ / \

[10 15] [21 37 44] [51 59] [63 72] [85 91]

判断没有破坏B+树的性质,删除完毕

Eg.3 删除51,首先找到51所在节点(第三个节点),删除之

[59 97]

/\

[15 44 59][72 97]

/ | \ / \

[10 15] [21 37 44] [59] [63 72] [85 91 97]

破坏了B+树的性质,从该节点的兄弟节点(左边或右边)借节点44

[59 97]

/\

[15 37 59][72 97]

/ | \ / \

[10 15] [21 37] [44 59] [63 72] [85 91 97]

并修改相应键值,判断没有破坏B+树,完毕

Eg.4 在Eg.3的基础上删除59,首先找到59所在叶节点(第三个节点),删除之

[59 97]

/ \

[15 37 59] [72 97]

/ |\ / \

[10 15] [21 37] [44] [63 72] [85 91 97]

破坏B+树性质,尝试借节点,无效(因为左兄弟节点被借也会破坏B+树性质),合并第二第三叶节点并调整键值

[44 97]

/ \

[15 44][72 97]

/ \/ \

[10 15] [21 37 44] [63 72] [85 91 97]

完毕

Eg.5 在Eg.2的基础上删除63,

[59 91]

/\

[15 44 59] [72 91]

/ | \/ \

[10 15] [21 37 44] [51 59] [72] [85 91]

合并第四五叶节点并调整键值

[59 91]

/\

[15 44 59] [91]

/ | \ |

[10 15] [21 37 44] [51 59] [72 85 91]

发现第二层的第二个节点不满足B+树性质,从第二层的第一个节点借59,并调整键值

[44 91]

/\

[15 44][59 91]

/ \ / \

[10 15] [21 37 44] [51 59] [72 85 91]

一个 B-Tree 是一种针对在块设备上优化 *** 作的数据结构。块设备或磁盘有相当重要的数据访问延迟，尤其是机械硬盘。在随机位置检索单个字节并不比检索更大的数据花费的时间更少。这是 B-Tree 的基本原理，InnoDB 使用的数据页为 16KB。让我们尝试简化 B-Tree 的描述。B-Tree 是围绕这键来组织的数据结构。键用于搜索 B-Tree 内的数据。B-Tree 通常有多个级别。数据仅存储在最底层，即叶子节点。其他级别的页面（节点）仅包含下一级别的页面的键和指针。如果要访问键值的数据，则从顶级节点-根节点开始，将其包含的键与搜索值进行比较，并找到要在下一级访问的页面。重复这个过程，直到你达到最后一个级别，即叶子节点。理论上，每个 B-Tree 级别的读取都需要一次磁盘读取 *** 作。在实践中，总是有内存缓存节点，因为它们数量较少且经常访问，因此适合缓存。一个简单的三级 B-Tree 结构

---