6-PostgreSQL 哈希索引原理浅析（文一）.pptx

1、PostgreSQL 哈希索引原理浅析,应急管理大学文一,写在前面,2,索引，作为数据库领域的一个重要方面，为提升数据访问效率提供了有力的支撑。而本次报告中，我们将聚焦 PostgreSQL 哈希索引的实现原理展开研究，力争帮助各位建立一个综合而全面的理解。本次报告分为如下部分：知识准备涵盖 PostgreSQL 的设计原理、系统表等同哈希索引有所关联的部分哈希算法原理以及工程实现解析阐述哈希索引所依据的算法思想，并从哈希索引表的组建与元组记录插入分析哈希索引的原理拓展延伸一些额外的知识以及有用的经验分享,知识准备：先从一个宏观视角理解 PostgreSQL,3,要点：PostgreSQL 高

2、度重视可定制化，但是其根本依旧是一种关系型的数据库但是我们可以依靠关系模型的灵活性，在一定程度上模拟其它的存储业界案例：Apache OpenDAL 的 PostgreSQL Service 部分,知识准备：先从一个宏观视角理解 PostgreSQL,4,要点：OpenDAL 的 PostgreSQL 服务部分，本质上就是用数据表的存储“模拟文件系统”这种做法对于通用性而言非常聪明，但是涉及不了根本性（这也是为什么不能单纯依靠 PG 索引可定制化实现真正的多数据模型）本实验复现参考使用 OpenDAL 连接 PostgreSQL一文,知识准备：先从一个宏观视角理解 PostgreSQL,5,这

3、种设计思想，体现到内核 API 上面就是所有的内核开放设计 API均带着浓浓的“数据表”味儿索引的核心作用：一、加快用户查找 Tuple 的速度二、可独立提供数据（Index-Only Scan）同时指出，对比 MySQL，PostgreSQL 在这方面的可定制化“并没有那么高”,MySQL 把“Table”与“Index”两种 Access Methon 直接统一为“存储引擎”并开放设计这种更大的灵活度，客观上让 MySQL 的存储引擎生态优于 PostgreSQL,知识准备：从一个宏观视角理解 PG 索引,6,现在，我们继续把目光放在内核设施本身上面。可以发现，工程的实现实际上就是理论的延

4、伸。我们只需要抓住 Index-Access-Method 这条“主轴”，既可以顺利地理解好 Hash Index 的实现。这就需要我们找到一个切入点，参考下文。,知识准备：pg_am 系统表 与 IndexAmRoutine 接口,7,要点:pg_am 存储着所有的 Index-Access-Method 的注册信息（可通过 pg_am.dat 直接得到）通过 amhandler 所指向的内核C语言函数，即可以找到有关索引的各个实现接口IndexAmRoutine 结构描述着一个索引所需要实现与可以实现的接口函数，并指导 PostgreSQL 将元祖的键值进行传递,知识准备：系统表 与 BK

5、I 文件,8,要点:通过 select.from;的上层接口方式，可以用一个更为直观的方式，将有关信息查询出来，事半功倍理解 BKI 文件、pg_xxx.h 文件起到的支撑作用，对于理解如何自己定制索引非常重要,知识准备：系统表 与 BKI 文件,9,要点:PostgreSQL 把“关系型数据”的思想同样运用到系统信息的管理上catalog 目录的 pg_xxx.h 是诸多系统表的“原始形态”（Perl 脚本将会负责改写他们为正式的 pg_xxx_d.h 形态）pg_xxx.dat 将会指导向系统表里面写入初始数据,知识准备：pg_am 系统表 与 IndexAmRoutine 接口,10,h

6、ashhandler 函数：负责在 Relation 中注册处理各个哈希索引处理函数核心逻辑就是分配一块内存，存储 IndexAmRoutine 结构，并将其反馈于 PostgreSQL,开始理解哈希索引：哈希算法简介,11,哈希算法的思想：通过某种映射算法，将一个数据映射到唯一对应的序号，再将其存储起来。因为“一一对应”，所以哈希算法大幅度提升了查找数据的效率，在不存在碰撞的情况下，时间远远短于顺序查找。缺点在于，因为映射算法的结果是无序的，因此，哈希表很难支持按照某种范围提取数据，以及排序等工作，这也是 PostgreSQL 哈希索引不支持 ORDEY BY 的原因。,开始理解哈希索引：动