Gists

Data Structure

Data Structure

树

二叉树的删除

如果是排序树,节点的删除分为三种情况:如果被删除的是叶子节点,那么直接删除;如果被删除的节点只有左子树或右子树,那么用子树替换该节点;不然,使用左值树最大值节点或右子树最小值节点替换该节点。

彻底理解B树和B+树!为何它们常用在数据库中?

B-tree 是 M-way-Tree 的约束版本。在创建 M-way 的 B-tree 时,需要持续往一个目标节点塞入 M-1 个元素。如果目标节点塞不下,则分裂出一个新节点存放新元素,并将目标节点中部分元素取出,另新建一个低层节点置于目标节点和新节点的上层,并连接。每次分裂出节点时,所有改变了元素的节点都需要重新调整其子节点的指向。

B+-tree 相比 B-tree 有几点改变:

  • B+-tree 允许重复索引值的元素,底层节点的所有元素都能在高层节点找到一份拷贝,这也意味着 B+-tree 的叶子是全索引。
  • B-tree 每一个元素都携带了指针指向索引物理位置,而 B+-tree 的指针位于叶子节点。
  • B+-tree 的叶子节点作为链表相连。

原始的 B-tree 是面向磁盘设计的:

  • 有序、平衡的多级储存结构
  • 面向磁盘设计,每一个节点都是磁盘块
  • 查找性能好,适合读密集负载
  • 就地更新(In-Place Update)
  • 写入性能差,分裂、合并等操作都是随机写

Copyright © 2024 Lionad - CC-BY-NC-CD-4.0