B Tree

2019-10-18

https://leetcode-cn.com/tag/dynamic-programming/

https://leetcode-cn.com/tag/dynamic-programming/

https://leetcode-cn.com/problems/unique-binary-search-trees/

BST，Binary Search Tree, Binary Sort Tree

插入

新插入节点总是叶子节点

删除

1. 如果待删除的节点是叶子节点，那么可以立即被删除

2. 如果有一个子节点，要将下一个子节点上移到当前节点，即替换

3. 如果有两个子节点，则将其右子树的最小数据替换此节点的数据

效率

• 查找：最佳情况Olog(n), 最坏情况O(n)

• 插入：最佳情况Olog(n), 最坏情况O(n)

• 删除：最佳情况Olog(n), 最坏情况O(n)

big-endian

即大端小端

对于整型、长整型等数据类型，Big endian 认为第一个字节是最高位字节（按照从低地址到高地址的顺序存放数据的高位字节到低位字节）；而 Little endian 则相反，它认为第一个字节是最低位字节（按照从低地址到高地址的顺序存放据的低位字节到高位字节）。

MutableBigInteger是BigInteger类的另一个版本，它的特点是不创建临时对象的前提上使调用程序得到象BigInteger类型的返回值(称为可变对象技术)。因为大整数的除法是由大量的其他算术操作组成的，所以需要大量的临时对象，而完成大量的操作而不创建新的对象可以极大地改善程序的性能，（因为创建对象的代价是很高的）所以在Java的大整数类中使用MutableBigInteger类中的方法来执行大整数除法

源码

https://codeday.me/bug/20170818/53558.html

https://www.hollischuang.com/archives/176

由于 BigDecimal 对象是不可变的，这些方法中的每一个都会产生新的 BigDecimal 对象。因此，因为创建对象的开销，BigDecimal 不适合于大量的数学计算，但设计它的目的是用来精确地表示小数

b树

平衡多路查找树

B树相对于平衡二叉树的不同是，每个节点包含的关键字增多了，特别是在B树应用到数据库中的时候，数据库充分利用了磁盘块的原理（磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来）把节点大小限制和充分使用在磁盘快大小范围；把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度

b+树

速度完全接近于二分法查找

B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加

所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样

非叶子节点的子节点数=关键字数

边结尾数据都会保存右边节点开始数据的指针

相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快

B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高

B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描

B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

b×树

在B+树的基础上因其初始化的容量变大，使得节点空间使用率更高，而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少