database - Yelp 是如何处理 "Open now"的？

Question

Yelp 如何存储商家的时间信息以及它如何能够如此快速地查询和过滤掉“正在营业”的商家？它不需要一些实时处理来解析日期-日期-时间信息并将其与“现在”进行比较。

Answer 1

我会使用 segment tree .它是一种存储区间的数据结构，可以有效地查询一个点属于哪些区间。间隔可以只是整数间隔，如 (2,3)、(5,9)、(10, 15) 等，

在 yelp 案例中，它们是代表企业工作时间的时间间隔。以毫秒分辨率获取当前时间是微不足道的。例如，在 java 中，您将获得 System.currentTimeMillis()。然后，如果您在线段树中存储了间隔，则您可以查询当时(现在)开放的间隔(进而是哪些企业)。就时间复杂度而言，您可以在 O(log n + k) 中完成此操作，其中 n 是数据库中的企业总数，k 是现在开放的企业数量。