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）
写入性能差，分裂、合并等操作都是随机写

C++

DEPRESSION