知识卡片

普通读书笔记卡 · 2580.b.1.c.1.h.2.b.3.a.4

端点扫描计算区间交并

理解等级:中级

区间端点包含值、左右端和开闭标记。对内部无重叠的已规范化区间序列,按端点扫描维护覆盖次数:求并保留被任一序列覆盖部分,求交保留两者同时覆盖部分;边界包含性仍须参与比较。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 7 处

    参考来源

    - 位置:《TiDB源码阅读系列文章》第13章《TiDB 源码阅读系列文章(十三)索引范围计算简介》(来源项目:book-sources;源文件:extracted/TiDB源码阅读系列文章/_epub-src/OEBPS/Text/TiDB 源码阅读系列文章(十三)索引范围计算简介.html;阅读段落 32,35,38,39,40,41,42;均为书中版本) - 结论依据:原文对端点扫描计算区间交并给出上述机制或边界;本卡把已读说明整理为可独立理解的解释。 - 原始内容:这种情况下,输入的表达式为 Column op Constant 形式的简单表达式由 OR 以及 AND 连接而成。我们对每一个具体的操作符,都设计了一段对应的计算 range 的逻辑,当遇到 AND 或者 OR 时,会对两个区间求交或者求并。在 point.go 中有一个 builder …… 每个 point 代表区间的一个端点,其中的 excl 表示端点为开区间的端点还是闭区间的端点。start 表示这个端点是左端点还是右端点。 …… 除了对具体函数的处理外,pointer.go 中还有区间交和区间并的操作。intersection 和 union 分别代表区间交和区间并。两个函数的逻辑均通过 merge 方法进行处理,通过传入一个 flag 来区分。merge 函数做了如下两个假设: …… a, b 两个区间均已经做过去重 …… 单个区间序列内部不会有重叠的部分 …… merge 函数使用 inRangeCount 来记录当前位置被 a, b 两个区间序列覆盖的情况。区间求并的情况时,只要 a, b 两个区间序列中有一个区间序列覆盖便可以作为解输出,被两个区间同时覆盖的端点必然是属于一个更大的区间的内部不需要输出。所以当 inRangeCount 为 1 …… 当区间求交时,需要两个序列都覆盖到才是可以输出的端点,所以当 inRangeCount 为 2 时,即为需要输出的区间端点。