B Tree
30 August, 2020
这篇文章以数据库存储的数据结构来引出本文的重点B树,以及后面还有另一种数据结构B+树.
试想, 如果你想持久化大量的数据在硬盘上, 同时还希望能高效的查询和修改他们, 你会怎么做, 使用哪种数据结构.
数组和链表, 他们的缺点很明显, 我们寻找数据需要遍历整个数据结构, 试想一下你的数据库中有50PB的数据, 这个开销是我们无法接受的.
哈希表, 通过给定的数据通过Hash函数生成对应的索引, 能非常高效的找到对应的数据. 但是, 哈希表不能用于范围查询.
二叉树, 一种使用二分法作为查询算法的数据结构, 在内存中, 二叉树的效率确实非常高, 但是如果是在硬盘上, 每次读取节点, 都需要进行一次IO, 随着数据量的增大, 深度逐渐加深, 二叉树的效率就会大大降低.
B Tree
B树存在一些和二叉树不一样的地方: 二叉树每个节点只保存一份数据以及两个指针, B树在每个节点都可以保留一样数量的数据和指针, 指针的数量为数据的数量+1.
在B树中还有存在一个概念, 阶数, 它决定了该B树每个节点应该有多少数据以及指针.
Rules
-
排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；例如一个节点能存放3份数据, 该数据需要从左到右增序存放, 1, 2, 3.
-
子节点数：非叶节点的子节点数>1，且<=M ，且M>=2，空树除外(注：M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉)；
-
关键字数：子节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个(注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);
-
所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子;
Find
我们用一个图和一个实际的例子来理解B树(这里为了理解方便我就直接用实际字母的大小来排列C>B>A):
如上图我要从上图中找到E字母，查找流程如下:
-
获取根节点的关键字进行比较，当前根节点关键字为M，E<M(26个字母顺序)，所以往找到指向左边的子节点(二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点)；
-
拿到关键字D和G，D<E<G 所以直接找到D和G中间的节点；
-
拿到E和F，因为E=E 所以直接返回关键字和指针信息(如果树结构里面没有包含所要查找的节点则返回null).
Insert
下次更新.