| 数据结构 | 实现原理 | key查询方式 | 查找效率 | 存储大小 | 插入、删除效率 |
|---|---|---|---|---|---|
| Hash | 哈希表 | 支持单key | 接近O(1) | 小，除了数据没有额外的存储 | O(1) |
| B+树 | 平衡二叉树扩展而来 | 单key,范围，分页 | O(Log(n) | 除了数据，还多了左右指针，以及叶子节点指针 | O(Log(n)，需要调整树的结构，算法比较复杂 |
| 跳表 | 有序链表扩展而来 | 单key，分页 | O(Log(n) | 除了数据，还多了指针，但是每个节点的指针小于<2,所以比B+树占用空间小 | O(Log(n)，只用处理链表，算法比较简单 |
| 数据结构 | 实现原理 | key查询方式 | 查找效率 | 存储大小 | 插入、删除效率 |
|---|---|---|---|---|---|
| Hash | 哈希表 | 支持单key | 接近O(1) | 小，除了数据没有额外的存储 | O(1) |
| B+树 | 平衡二叉树扩展而来 | 单key,范围，分页 | O(Log(n) | 除了数据，还多了左右指针，以及叶子节点指针 | O(Log(n)，需要调整树的结构，算法比较复杂 |
| 跳表 | 有序链表扩展而来 | 单key，分页 | O(Log(n) | 除了数据，还多了指针，但是每个节点的指针小于<2,所以比B+树占用空间小 | O(Log(n)，只用处理链表，算法比较简单 |
名师互学网 版权所有 (c)2021-2022 ICP备案号：晋ICP备2021003244-6号
