Skip to content

Latest commit

 

History

History
154 lines (123 loc) · 8.7 KB

README.V3.md

File metadata and controls

154 lines (123 loc) · 8.7 KB
Raw

V3版本

  • 源码位置: src/main/com/BPlusTree/V3
  • 测试文件位置: test/java/com/BPlusTree/V3

特点

版本 插入 删除 查找 修改 持久化
V3 √ √ √ √ ×
  • 节点页使用链表的形式

    由于官方库的链表不能直接操作节点, 且不有序, 相当于每次都要从头节点开始, 效率很低, 所以这里自己实现了一个有序链表 : src/main/java/com/BPlusTree/SortedLinkList

  • 数据节点用有序链表串起来 (V2版本是使用的普通链表串联节点页)
  • 包含普通索引和唯一索引两种方式

结构

  • 一个父节点对应一个子页面(子节点集合), 父节点的值是子节点里的最大值
  • 节点页使用链表的形式
  • 数据节点用有序链表串起来

img.png

算法

查找

在当前页开始查找索引为 key 对应的节点 leNode

  1. 查找当前页第一个 >=key 的节点

如果没找到, 直接返回 null

  1. 如果当前页不为叶子节点, 在子页 leNode.children 页继续查找
  2. 为叶子节点, 如果 leNode.key != key, 没有满足要求的节点, 返回 null
  3. 如果为唯一索引, 只存在一个满足要求的值, 直接返回 leNode.data
  4. 不为唯一索引, 可能存在多个满足要求的值, 从 leNode.leafTreeNode 开始在叶子节点链表查找所有索引为 key 的值

更新

与查找的思路是一样的, 查找是查找满足要求的节点, 更新里找到这些节点后, 把这些节点的值更新成新值就可以了

插入

在当前页开始尝试插入键值对 [key: value]

  1. 在当前页查找第一个 >= key 的节点 leNode
  2. 如果为叶子节点
    1. 如果 leNode 为 null, 表示 key 是最大值
      1. 维护叶子链表: 在当前页最后一个索引节点后面添加新叶子节点

        如果当前页没有索引, 当且仅当什么也没有时才可能存在这种情况,此时叶子链表也为空, 直接尾部添加一个叶子节点即可

      2. 当前页在末尾插入 [key: value]
    2. leNode不为null
      1. 维护叶子链表: 在 leNode 对于的叶子节点前面添加新叶子节点
      2. 当前页在 leNode 前面插入新节点
    3. 如果当前页节点个数超出阶数, 分裂当前节点(见分裂算法)
  3. 不为叶子节点
    1. 如果 leNode 为 null, 表示 key 是最大值
      1. 更新最大值(即最后一个节点)的索引为 key
      2. 在最后一个节点的子节点页 尝试插入 [key:value]
    2. leNode不为null, 在子节点页 leNode.children 尝试插入新节点

删除

需要考虑一个比较复杂的情况就是非唯一索引, 删除一个 key 可能要删除多个节点, 这些节点可能在多个页里面

在当前页开始尝试删除键 key 对应的值

  1. 在当前页查找第一个索引 >= key 的节点 leNode
  2. 如果 leNode 为 null, 没找到, 直接 return
  3. 如果当前页为叶子页, 从 leNode 开始遍历删除索引为 key 的节点
    1. 如果 leNode.key 不等于 key, 跳出循环
    2. 维护叶子链表: 叶子链表里直接删除这个节点
    3. 当前页删除 eNode
    4. 可能移除了最后一个节点
      1. 如果是删除了一整页, 需要删除索引
      2. 只是删除了最大值, 需要更新索引
      3. 继续删除下一页
    5. 如果当前页节点个数 < degree/2, 拓展|合并 当前页(见 拓展|合并 算法)
    6. 更新 leNode

      如果影响了当前页结构, 需要重新查找一遍, 否则直接取 next 就可以了

    7. 如果 leNode 为 null, 没找到, 跳出循环
  4. 如果当前页不为叶子页, 去子页 leNode.children 继续尝试删除

分裂算法

将当前页分成左右两个界面

条件: 页面的阶数 > 阶数

  1. 为根页, 分裂成两个子页, 根页面设置两个字页索引
  2. 不为根页, 分裂成两个页, 父页面新添加一个索引, 如果父页面节点数也超出阶数, 继续分裂父页面

拓展|合并 算法

将当前页拓展到节点个数 >= 阶数/2

条件:

  1. 不为根页
  2. 当前页的节点数 < degree/2
  1. 如果没有兄弟页, 只用考虑一种情况: 当前页没有节点了, 需要删除父页的索引(见删除索引算法)
  2. 如果有兄弟页(这里优先考虑右边的兄弟)
    1. 如果兄弟页的节点个数 > degree/2, 向兄弟借一个
    2. 如果兄弟页的节点个数也不够, 合并兄弟页
    3. 更新自己或者兄弟页的索引(见更新索引算法)

更新索引算法

条件: 不为根页

不单是更新当前页在父页里的索引, 如果父页里的索引为最后一个节点, 需要继续向上更新父页的索引

删除索引算法

条件: 不为根页

删除当前页在父页里的索引后, 需要考虑两种情况:

  1. 父页面里的节点被删完了, 需要继续向上删除父页面的索引
  2. 删除的是父页面里的最大值, 需要更新父页的索引

父子节点关系

current 表示当前页, parent 表示父页

  1. current.parentPage = parent,
  2. current.parentKeyNode in parent.nodes // 索引
  3. current.parentKeyTreeNode.children = parent // 索引节点子页面
  4. 对于 current.nodes:
    • 如果 current 不是叶子, node.children -> current 是 node.children 的父界面, 对 node.children 进行第 1, 2, 3步
    • node.page = current // 所属页
    • node.keyListNode in current.nodes // 索引链表节点

心得

V3版本花了我6天, 之所以花这么长时间, 不是因为它难, 是因为太复杂了, 边界情况太多根本考虑不过来, 写完我也有了一些自己的心得

  1. 不要过度追求算法时间复杂度 —— 得看实际应用场景

做为一名科班出身的开发者, 我总是追求更小的时间复杂度, 但是有的时候是真的没有必要

V1版本里的B+树节点页我选用的数组,我当时吭哧吭哧两天就写好了,虽然写的时候很快乐,算法写起来都很简单,但是我总感觉使用数组删除元素插入元素之类的会花费更久的时间,所以后面的版本我就想着用链表,于是我就掉进坑里了。

由于官方的链表不能直接操作节点(这不是比数组效率更低),而且我需要一个有序的链表,所以我就自己手搓了一套,在B+树的实现里很多地方都要手动操作链表节点,你套我我套你,还得保证唯一索引的唯一性以及有序性,典型的耦合程度太高。

而且我也在反思,B+树的节点页真的需要用到链表吗?

在数据库底层实现里一个节点页顶破天节点个数不超过1000个,算法的时间复杂度是考虑数据量很大的情况,很明显这里就不符合。就这么点数据量,使用数组真的会比链表慢?就算慢又能慢多少?而且使用链表的时候,为了考虑各种边界情况,写了一堆判断执行,先不说编写代码的时候的心智负担,单说判断这个操作,它在CPU里是很耗时间的。说不定90%的情况链表还比数组慢。

我们再看实际应用场景——数据库, 是把节点页保存在磁盘里的, 之所以使用B+树就是为了减少访问磁盘次数, 如果使用链表需要保存一些额外信息, 这导致一页能保存的节点就更少了, B+树的阶数减少, 对于同样的数据, 层数就越多, 层数越多, 需要访问磁盘的次数就越多, 而访问磁盘是很耗时的, 跟这个时间比起来, 优化的那点时间就是小鱼小虾。

一顿折腾下来, 我学到了一个道理 —— 不要过度追求算法时间复杂度, 算法时间复杂度考虑的是极端情况, 实际应用场景中很多时候都不是极端情况, 还是得看实际应用场景

  1. 不要过早优化 —— 大道至简

写代码的时候老是想着这里可以可以少一两个操作, 或者那里可以提取成一个通用函数, 为了优雅我必须给他优化一下。然后吭呲吭呲一顿写, 写完了去测试, 哦豁, 报错了。然后再复现一下问题, 思考了半天, 哦, 原来是我边界情况没考虑, 这还不简单, 加个判断不就行了。然后又去测试, 哦豁, 又报错了......

最后改的面目全非, 这个时候再看, 这代码真的优雅吗?

答案很明显

  • 第一, 易读性变得很差, 这明显不符合我的初衷
  • 第二, 鬼知道还有什么边界情况我还没考虑

所以后面我又改回最简单易懂的思路了, 谁都看得懂, 测试跑一遍就过。经历了前面各种折腾, 再看这种代码, 反而觉得赏心悦目, 这TM才叫优雅!

综上所述, 该优化的时候才优化, 不该优化的时候就该老老实实的写, 嫌弃这嫌弃那的, 这才哪到哪儿, 写代码的时候老是考虑未来那么久的事情, 只会增加自己现在的心智负担, 俗话说的好 —— 活在当下，珍惜眼前。