网站免费部署/seoaoo
1. B树和B+树的区别
(1) B-树的特点
-
所有关键字分布在整颗树节点中
-
每个树节点存储索引和数据
-
搜索有可能在非叶子结点结束，最好情况O(1)就能找到数据
(2) B+树的特点
-
所有关键字都只在叶子节点出现
-
内部节点不存储数据，仅起到索引作用
-
为所有叶子结点增加了一个链指针，相邻叶节点按大小顺序链接起来
-
查询时间复杂度固定为 O(log n)
-
B+树更适合外部存储。由于内节点无数据域，每个节点能索引的范围更大更精确
2. 排序算法
- 插入排序
- 直接插入排序
- 折半插入排序
- 希尔排序
- 交换排序
- 冒泡排序
- 快速排序
- 选择排序
- 简单选择排序
- 堆排序
- 归并排序
- 基数排序
| 排序法 | 平均时间 | 最差情形 | 稳定度 | 额外空间 |
|---|---|---|---|---|
| 冒泡排序 | O(n2n^2n2) | O(n2n^2n2) | 稳定 | O(1) |
| 选择排序 | O(n2n^2n2) | O(n2n^2n2) | 不稳定 | O(1) |
| 插入排序 | O(n2n^2n2) | O(n2n^2n2) | 稳定 | O(1) |
| 希尔排序 | O(nlogn) | O(ns) 1<s<2 | 不稳定 | O(1) |
| 快速排序 | O(nlogn) | O(n2) | 不稳定 | O(nlogn) |
| 归并排序 | O(nlogn) | O(nlogn) | 稳定 | O(1) |
| 堆排序 | O(nlogn) | O(nlogn) | 不稳定 | O(1) |
| 基数排序 | O(logRB) | O(logRB) | 稳定 | O(n) |