day4, 2021 年 12 月 20 日，周一

题目

有B+Tree/Hash_Map/STL Map三种数据结构。对于内存中数据，查找性能较好的数据结构是（），对于磁盘中数据，查找性能较好的数据结构是（）。

  1. Hash_Map/B+Tree
  2. STL_Map/B+Tree
  3. STL_Map/Hash_Map
  4. B+Tree/Hash_Map

每日一题 day4.001.png

解析

答案：1

  • Hash操作能根据散列值直接定位数据的存储地址，设计良好的hash表能在常数级时间下找到需要的数据，但是更适合于内存中的查找。
    • 查找时间复杂度：O(1)。
  • B+树是一种是一种树状的数据结构，适合做索引，对磁盘数据来说，索引查找是比较高效的。
    • 查找时间复杂度：O(log(N))。
  • STL_Map的内部实现是一颗红黑树，但是只是一棵在内存中建立二叉树，不能用于磁盘操作，而其内存查找性能也比不上Hash查找。
    • 查找时间复杂度：O(log(N))。

因此对于内存中数据，查找性能较好的数据结构是Hash_Map，对于磁盘中数据，查找性能较好的数据结构是B+Tree。

HashMap

在内存中构建的。
HashMap底层实现原理：https://juejin.cn/post/6844903744711163911
image.png

B+树

平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了：https://zhuanlan.zhihu.com/p/27700617
为什么 MySQL 使用 B+ 树：https://draveness.me/whys-the-design-mysql-b-plus-tree/
image.png

STL Map

就是红黑树。
30张图带你彻底理解红黑树：https://www.jianshu.com/p/e136ec79235c
image.png