Interview Q&A STL

B 树（B-tree）、B+ 树（B+-tree）

特点

  • 一般化的二叉查找树（binary search tree）
  • “矮胖”，内部（非叶子）节点可以拥有可变数量的子节点（数量范围预先定义好）

应用

  • 大部分文件系统、数据库系统都采用 B 树、B+树作为索引结构

区别

  • B+树中只有叶子节点会带有指向记录的指针（ROWID），而 B 树则所有节点都带有，在内部节点出现的索引项不会再出现在叶子节点。
  • B+树中所有叶子节点都是通过指针连接在一起，而 B 树不会。

B 树的优点

  • 对于在内部节点的数据，可直接得到，不必根据叶子节点来定位。

B+树的优点

  • 非叶子节点不会带上 ROWID，这样，一个块中可以容纳更多的索引项，一是可以降低树的高度。二是一个内部节点可以定位更多的叶子节点。
  • 叶子节点之间通过指针来连接，范围扫描将十分简单，而对于 B 树来说，则需要在叶子节点和内部节点不停的往返移动。

STL 容器

容器 底层数据结构 时间复杂度 有无序 可不可重复 其他
array 数组 随机读改 O(1) 无序 可重复 支持随机访问
vector 数组 随机读改、尾部插入、尾部删除 O(1) 头部插入、头部删除 O(n) 无序 可重复 支持随机访问
deque 双端队列 头尾插入、头尾删除 O(1) 无序 可重复 一个中央控制器 + 多个缓冲区，支持首尾快速增删，支持随机访问
forward_list 单向链表 插入、删除 O(1) 无序 可重复 不支持随机访问
list 双向链表 插入、删除 O(1) 无序 可重复 不支持随机访问
stack deque / list 顶部插入、顶部删除 O(1) 无序 可重复 deque 或 list 封闭头端开口，不用 vector 的原因应该是容量大小有限制，扩容耗时
queue deque / list 尾部插入、头部删除 O(1) 无序 可重复 deque 或 list 封闭头端开口，不用 vector 的原因应该是容量大小有限制，扩容耗时
priority_queue vector + max-heap 插入、删除 O(log2n) 有序 可重复 vector 容器+heap 处理规则
set 红黑树 插入、删除、查找 O(log2n) 有序 不可重复
multiset 红黑树 插入、删除、查找 O(log2n) 有序 可重复
map 红黑树 插入、删除、查找 O(log2n) 有序 不可重复
multimap 红黑树 插入、删除、查找 O(log2n) 有序 可重复
unordered_set 哈希表 插入、删除、查找 O(1) 最差 O(n) 无序 不可重复
unordered_multiset 哈希表 插入、删除、查找 O(1) 最差 O(n) 无序 可重复
unordered_map 哈希表 插入、删除、查找 O(1) 最差 O(n) 无序 不可重复
unordered_multimap 哈希表 插入、删除、查找 O(1) 最差 O(n) 无序 可重复