索引 - 原理

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+Tree

B+Tree: B-Tree变种

Hash

Hash优缺点明显

参考

上一篇 下一篇

猜你喜欢

热点阅读