打工四年总结的数据库知识点( 三 ) .font_s.ios.pgcarticle

If the bucket is not full(a most b - 1 entries after the insertion ， b 是节点中的元素个数，一般是页的整数倍),add tht record.

Otherwise,before inserting the new record split the bucket. original node has 「(L+1)/2」itemsnew node has 「(L+1)/2」items Move 「(L+1)/2」-th key to the parent,and insert the new node to the parent.Repeat until a parent is found that need not split.

If the root splits,treat it as if it has an empty parent ans split as outline above.

B-trees grow as the root and not at the leaves.
删除
和插入类似，只不过是自下而上的合并操作。
树的常见特性AVL 树
平衡二叉树，一般是用平衡因子差值决定并通过旋转来实现，左右子树树高差不超过1 ，那么和红黑树比较它是严格的平衡二叉树，平衡条件非常严格（树高差只有1），只要插入或删除不满足上面的条件就要通过旋转来保持平衡。由于旋转是非常耗费时间的。所以 AVL 树适用于插入/删除次数比较少，但查找多的场景。
红黑树
通过对从根节点到叶子节点路径上各个节点的颜色进行约束，确保没有一条路径会比其他路径长2倍，因而是近似平衡的。所以相对于严格要求平衡的AVL树来说，它的旋转保持平衡次数较少。适合，查找少，插入/删除次数多的场景。（现在部分场景使用跳表来替换红黑树，可搜索“为啥 redis 使用跳表(skiplist)而不是使用 red-black？”）
B/B+ 树
多路查找树，出度高，磁盘IO低，一般用于数据库系统中。
B + 树与红黑树的比较红黑树等平衡树也可以用来实现索引，但是文件系统及数据库系统普遍采用 B+ Tree 作为索引结构，主要有以下两个原因：
（一）磁盘 IO 次数
B+ 树一个节点可以存储多个元素，相对于红黑树的树高更低，磁盘 IO 次数更少。
（二）磁盘预读特性
为了减少磁盘 I/O 操作，磁盘往往不是严格按需读取，而是每次都会预读。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道。每次会读取页的整数倍。
操作系统一般将内存和磁盘分割成固定大小的块，每一块称为一页，内存与磁盘以页为单位交换数据。数据库系统将索引的一个节点的大小设置为页的大小，使得一次 I/O 就能完全载入一个节点。
B + 树与 B 树的比较B+ 树的磁盘 IO 更低
B+ 树的内部节点并没有指向关键字具体信息的指针。因此其内部节点相对 B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
B+ 树的查询效率更加稳定
由于非叶子结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
B+ 树元素遍历效率高
B 树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题， B+树应运而生。 B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而 B 树不支持这样的操作（或者说效率太低）。
MySQL 索引索引是在存储引擎层实现的，而不是在服务器层实现的，所以不同存储引擎具有不同的索引类型和实现。
B+ Tree 索引是大多数 MySQL 存储引擎的默认索引类型。

因为不再需要进行全表扫描，只需要对树进行搜索即可，所以查找速度快很多。
因为 B+ Tree 的有序性，所以除了用于查找，还可以用于排序和分组。
- 上一页
- 1
- 2
- 3
- 4
- 5
- 6
- 下一页