索引 - 原理
2018-09-07 本文已影响9人
诺之林
复杂度
| 数据结构 | 查找 | 插入 | 删除 |
|---|---|---|---|
| 数组 | O(n) | O(n) | O(n) |
| 有序数组 | O(logn) | O(n) | O(n) |
| 链表 | O(n) | O(1) | O(1) |
| 有序链表 | O(n) | O(1) | O(1) |
| 二叉树 | O(n) | O(n) | O(n) |
| 有序二叉树 | O(logn) ~ O(n) | O(logn) ~ O(n) | O(logn) ~ O(n) |
| B-Tree | O(logn) | O(logn) | O(logn) |
| Hash | O(1) | O(1) | O(1) |
有序二叉树又称二叉查找树
B-Tree
B-Tree: 平衡多叉查找树
-
B(balanced): 左右子树层级相差<=1 相比非平衡提升最优查找效率
-
多叉: 子树可以不仅仅只有两个 相比二叉树减少I/O操作以提升查找效率
B+Tree
B+Tree: B-Tree变种
-
非叶子只存储键值而叶子只存储数据 相比BTree减少I/O操作以进一步提升查找效率
-
叶子有序链接 -> 提升范围查找效率
Hash
Hash优缺点明显
-
不支持排序
-
不支持部分和范围查找
