数据结构：检查数据库中是否存在记录？
Data Structures: Checking if a record exists in a database?
这是一道面试题："Which data structure would you use to check if a record exists in a database?"
我的直接答案是二叉搜索树。
面试官没有评论，继续下一个问题。这个问题的答案是什么？
这个问题有很多答案，这完全取决于这条记录到底包含什么以及你想用它做什么。
我会回答 hash table，因为摊销案例的搜索时间非常快 (O(1))。它还具有快速插入和删除的额外好处。
如果您打算对整个记录（即第 n 个最小的工资）进行操作，则二叉搜索树可以很好地工作，但如果您所做的只是在数据库中搜索是否存在，那么您正在寻找搜索时间更长 运行 次。
有很多可以接受的答案，在这样的面试中，迅速而自信地提供一个可以接受的答案比给出完美的答案更重要。
Binary trees 绝对是一个有效的答案。恭喜！
但是对于数据库，B-trees（"B" 代表 "balanced"）会更加推荐。 B 树是二叉树的推广，其中每个节点都有两个以上的子节点。这使得该数据结构更有效地优化磁盘读取访问。该结构还需要比二叉树更少的重新平衡，这也意味着更少的磁盘写入访问。
如果您对性能考虑感兴趣，this SO answer 会对两种结构进行有趣的比较。
现在，仅针对记录，在某些应用领域有更专业的结构，例如 R-trees 用于 3D 空间数据，或者哈希表，如果您考虑寻找唯一键并准备牺牲一些space 以获得更快的速度。
编辑： 流行数据库的一些示例（并非详尽无遗！）：
- sqllite 使用 b 树（并且有一个 r 树扩展）
- BerkleyDB 使用 B 树和哈希索引
- MySQL 使用 B 树和哈希（ans 也有 r 树）
- Postgresql 使用 B 树、r 树、哈希和其他几个
- SQLserver 显然也使用 B 树
这是一道面试题："Which data structure would you use to check if a record exists in a database?"
我的直接答案是二叉搜索树。
面试官没有评论，继续下一个问题。这个问题的答案是什么？
这个问题有很多答案，这完全取决于这条记录到底包含什么以及你想用它做什么。
我会回答 hash table，因为摊销案例的搜索时间非常快 (O(1))。它还具有快速插入和删除的额外好处。
如果您打算对整个记录（即第 n 个最小的工资）进行操作，则二叉搜索树可以很好地工作，但如果您所做的只是在数据库中搜索是否存在，那么您正在寻找搜索时间更长 运行 次。
有很多可以接受的答案，在这样的面试中，迅速而自信地提供一个可以接受的答案比给出完美的答案更重要。
Binary trees 绝对是一个有效的答案。恭喜！
但是对于数据库，B-trees（"B" 代表 "balanced"）会更加推荐。 B 树是二叉树的推广，其中每个节点都有两个以上的子节点。这使得该数据结构更有效地优化磁盘读取访问。该结构还需要比二叉树更少的重新平衡，这也意味着更少的磁盘写入访问。
如果您对性能考虑感兴趣，this SO answer 会对两种结构进行有趣的比较。
现在，仅针对记录，在某些应用领域有更专业的结构，例如 R-trees 用于 3D 空间数据，或者哈希表，如果您考虑寻找唯一键并准备牺牲一些space 以获得更快的速度。
编辑： 流行数据库的一些示例（并非详尽无遗！）：
- sqllite 使用 b 树（并且有一个 r 树扩展）
- BerkleyDB 使用 B 树和哈希索引
- MySQL 使用 B 树和哈希（ans 也有 r 树）
- Postgresql 使用 B 树、r 树、哈希和其他几个
- SQLserver 显然也使用 B 树