知识卡片

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

有序索引在线建桶

理解等级:中级

索引流天然有序,初始桶深很小,桶数超限后把相邻桶两两合并并扩大深度。Region 结果合并时先处理交界处相同值,防止一个值分散在多个桶,再控制总桶数。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • TiDB 源码阅读系列文章(十二)统计信息(上) · 查看原书依据

      在建立索引列直方图的时候,由于不能事先知道有多少行的数据,也就不能确定每一个桶的深度,不过由于索引列的数据是已经有序的,因次可以采用如下算法:在确定了桶的个数之后,将每个桶的初始深度设为 1,用前面列直方图的创建方法插入数据,这样如果到某一时刻所需桶的个数超过了当前桶深度,那么将桶深扩大一

    • TiDB 源码阅读系列文章(十二)统计信息(上) · 查看原书依据

      在收集了每一个 Region 上分别建立的直方图后,还需要把每个 Region 上的直方图进行合并。对于两个相邻 Region 上的直方图,由于索引是有序的,因此前一个的上界不会大于后一个的下界。不过为了保证每个值只在一个桶里,我们还需要先处理一下交界处桶的问题,即如果交界处两个桶的上界和

    参考来源

    - 位置:《TiDB源码阅读系列文章》第12章《TiDB 源码阅读系列文章(十二)统计信息(上)》(来源项目:book-sources;源文件:extracted/TiDB源码阅读系列文章/_epub-src/OEBPS/Text/TiDB 源码阅读系列文章(十二)统计信息(上).html;阅读段落 26,27;均为书中版本) - 结论依据:原文对有序索引在线建桶给出上述机制或边界;本卡把已读说明整理为可独立理解的解释。 - 原始内容:在建立索引列直方图的时候,由于不能事先知道有多少行的数据,也就不能确定每一个桶的深度,不过由于索引列的数据是已经有序的,因次可以采用如下算法:在确定了桶的个数之后,将每个桶的初始深度设为 1,用前面列直方图的创建方法插入数据,这样如果到某一时刻所需桶的个数超过了当前桶深度,那么将桶深扩大一 …… 在收集了每一个 Region 上分别建立的直方图后,还需要把每个 Region 上的直方图进行合并。对于两个相邻 Region 上的直方图,由于索引是有序的,因此前一个的上界不会大于后一个的下界。不过为了保证每个值只在一个桶里,我们还需要先处理一下交界处桶的问题,即如果交界处两个桶的上界和