pg为何需要HOT
- 堆表是数据库中一种没有聚集索引的表类型，数据行按照插入顺序存储，类似于堆叠存放。
- 数据结构中的堆是一种特殊的完全二叉树，满足堆序性。
- 内存堆是操作系统或编程语言运行时管理动态内存分配的区域。
- PG的ctid是真正意义上的物理地址，由页号和行偏移量组成，格式如
(0,1)。
Primary, Secondary, and Clustered Indexes
主键索引：
- 主键索引，用于唯一标识表中的每一行数据。
- 在许多数据库系统中，尤其是那些默认将主键作为聚集索引的系统（如MySQL的InnoDB），主键索引必是聚集索引。
二级索引：
- 二级索引必是非聚集索引（Non-Clustered Index），即它指向的是主键（例如InnoDB）或数据行的指针（例如PG）。
- 在 PostgreSQL 中，所有索引在技术上都被认为是“二级索引”，因为它们与表的主数据区域（称为堆）是分开存储的。
聚集索引（Clustered Index）：
- 定义：聚集索引决定了表中数据的物理存储顺序。这意味着表的数据行按照聚集索引键值的顺序进行排序并存储。
- 特点：一个表只能有一个聚集索引，因为数据只能以一种方式物理排序。
堆表和索引组织表
堆表无序的，插入很快，哪里有空哪里插。堆表数据库没有聚集索引。
索引组织表是有序的，插入时为了保证b树是平衡的，需要不停渲染它。索引组织表数据库每张表必有一个聚集索引，如果没有就会自动创建一个。
- 堆表方案 Heap Table
堆表方案，由于索引是独立于数据存储的，因此可以有多个不同的索引服务于同一个表的不同列或组合列。
- PostgreSQL 支持多种类型的索引，包括 B-tree、Hash、GiST、SP-GiST、GIN 和 BRIN 索引。因为支持多种索引，所以加锁和mvcc的实现都非常复杂。每行有多个版本，相当于有多个CTID，为了保证CTID不丢，pg的索引需要维护这些CTID信息。
- mysql InnoDB只支持B-tree索引。InnoDB的二级索引不直接包含版本信息，但通过主键值间接支持MVCC。当通过二级索引访问数据时，需要先找到主键，再通过主键索引访问行数据并判断可见性。
PostgreSQL 使用堆表结构，数据行（元组）以无序方式存储在堆页面中，每个元组通过 CTID（物理地址：页号+行号） 唯一标识，索引直接指向 CTID。
更新问题：当一行被更新时，会生成新版本元组（MVCC 机制），旧元组保留（用于并发事务），当新元组与原元组不在同一页面时，新元组的 CTID 可能与旧元组不同，这时候所有索引都需要更新指向新的 CTID。
HOT更新（Heap-Only Tuples update）：CTID发生变化之后，继续让索引指向旧的CTID，而旧CTID指向的旧元组指向新元组的CTID，然后通过新旧元组之间的链表来找到最新版本。
HOT触发条件包括：
- 新旧元组必须在同一页
- 更新的列不涉及任何索引字段
- 索引组织表方案 Index Organized Table，IOT
支持覆盖索引。
无序主键，性能会贼差，因为b树是有序的，插入无序的主键时，数据库为了保证b树是平衡的会不停的渲染它。
只有IOT方案有索引覆盖和索引下推的概念，因为只有这个方案有回表这个概念，而索引覆盖和索引下推都是为了避免回表或者减少回表次数的。
InnoDB的回表就是回主键索引。
- 对比
堆表，就是一个堆，一个劲儿往里面扔，这就没有顺序了。那没有顺序，排序怎么解决？索引本身就是有序的，行数据有序是没有意义的。
mysql的主键是在b+树上排好序的，但是堆表咣咣往里扔是无序的，然后拿着地址在堆里找。
堆表有个好处，它不排序，它插入就很快，因为它不涉及到排序，就不需要往中间插。
像mysql，为了保证有序性，需要在1和3之间插入2，搞不好还会有页分裂。没有空间了，又要插进去，页得分裂。16k的页得分俩。页分裂之后会有空余问题，导致空间浪费。
堆表就是哪有空余就往哪里插，不用管顺序，所以insert非常快。
- 更新导致的写放大问题：
在 Postgres 的底层设计中，它的行数据是不可修改的，每个不可修改的行都叫做“元组”，每个唯一的元组都由一个唯一的 ctid 标识。
虽然历史版本会占用空间，但PostgreSQL的旧版本仅存储变更字段的增量信息。
不停的update会产生很多的垃圾。所以pg有vacuum命令来执行垃圾回收。
InnoDB 的行数据是可以修改的，虽然可修改但是也有写放大问题：
- InnoDB 是以数据页的形式组织数据的，Linux 上默认数据页的大小是 16K。
- 当你更改了一条记录时，最终会把这条记录所在的数据页整页刷回磁盘，你可能只是改了一个小字段，也许只有 4 个字节，可是最终却会导致 16K 字节的写入。
update: pg和InnoDB五五开
insert: pg的插入性能远高于InnoDB
- 插入同样多的数据，InnoDB花费的时间是postgres的10倍以上。
- 插入同样多的数据，InnoDB数据目录占用的空间是postgres的好几倍，因为mysql插入时需要写入好几份数据，binlog和redo log 和 todo log都有对应的数据。
- InnoDB采用“索引组织表”结构，当前版本存储在表空间（.ibd文件），历史版本存储在独立的回滚段（undo log）中。每次更新会生成完整的前像（undo log），即使只修改少量字段
select: pg的查询速度也比InnoDB快，因为pg第二索引直接指向元组的 ctid，而InnoDB的第二索引去读数据会经历“第二索引——主键——数据”的过程。
- mysql有三层B+树索引可以存多少行数据的概念，为何 postgres 没有这个概念呢
基于1024分支因子的计算：
- 假设每个索引项占14B（6B主键+8B指针），16KB页可存1024个索引项
- 三层结构：1个根节点 → 1024个二级节点 → 1024×1024=1,048,576个叶子节点
- 每个叶子节点存1024行数据（假设每行数据16B），总容量可达约10亿行
- 当超过10亿行，B+树会增加到四层
基于1170分支因子的计算：
- 假设每个索引项占16B（8B主键+8B指针），16KB页可存1170个索引项
- 三层结构：1个根节点 → 1170个二级节点 → 1170×1170=1,368,900个叶子节点
- 每个叶子节点存16行数据（假设每行数据1KB），总容量可达约1170×1170×16=21,902,400行（约2000万行）
- 当超过2000万行，B+树会增加到四层
所以，三层B+树索引可以存多少行数据受如下因素控制：
- 页大小（通常16KB）
- 每行数据大小（行越大，每页存储的行数越少）
- 索引项大小（由主键长度和指针长度决定）
为什么PostgreSQL没有"三层B+树"这个概念：
- PostgreSQL使用堆表（heap tables）存储数据，索引只是指向堆元组的指针，不直接包含数据
- 所以，pg没有回表的概念，其索引的叶子节点存放的是CTID，CTID到数据行的时间复杂度是O(1)，速度贼快
- 而InnoDB是索引组织表，数据行都在主键索引的叶子节点上，二级索引必须经过主键索引才能找到数据。一旦主键索引树超过三层，其查询效率就会贼低。
- InnoDB 和 PG 全表扫描的对比
InnoDB全表扫描会走主键索引么？
- 全表扫描实际上是从聚簇索引的第一个叶子节点开始，依次遍历所有记录，直到扫描完最后一个叶子节点。
PG每行数据就有多个版本，全表扫描的时候，会不会都扫出来呢？
- PostgreSQL每行数据都包含几个隐藏的系统列:
- xmin：创建该行版本的事务ID
- xmax：删除/锁定该行版本的事务ID(初始为0)
- cmin/cmax：事务内的命令标识符
- ctid：行版本在表中的物理位置
- 全表扫描时，PostgreSQL会检查每一行数据的系统列(xmin和xmax)来判断该行版本是否对当前事务可见：
- 如果xmin未提交或晚于当前事务快照 → 不可见
- 如果xmax已提交且早于当前事务快照 → 不可见(已删除)
- 否则可见
- 全表扫描会遍历表中的所有行，但只会返回对当前事务可见的版本
MVCC实现差异
PostgreSQL：堆内多版本
- 多版本数据直接存储在堆表中，旧元组可能长期存在，索引需支持通过 CTID 找到所有可见版本。
- HOT 通过在同一页面内维护版本链，减少索引对多版本的支持开销。
- 使用事务ID（txid）标识版本，每个事务开始时获取活跃事务列表形成快照，通过比较xmin、xmax与快照判断可见性
- 事务ID为32位整数，可能因耗尽引发“事务ID回卷”问题，需定期执行FREEZE操作
MySQL InnoDB：Undo 日志与聚集索引
- 多版本数据通过 Undo 日志管理，聚集索引中仅存储最新版本。
- 二级索引无需处理多版本，事务通过 ReadView 判断可见性，结合主键回表查询 Undo 日志。
innodb中 redo undo binlog 这三种日志的区别
binlog（二进制日志）
- 定义：binlog是MySQL服务器层的逻辑日志，记录所有对数据库的修改操作
- 层次：MySQL服务器层实现，与存储引擎无关
- 核心作用：主从复制、数据恢复和时间点恢复
redo log（重做日志）
- 定义：redo log是InnoDB存储引擎特有的物理日志，用于记录对数据页的物理修改
- 层次：存储引擎层(InnoDB)实现
- 核心作用：系统崩溃后，通过redo log重做已提交但未写入数据文件的修改
undo log（回滚日志）
- 定义：undo log是InnoDB存储引擎的逻辑日志，记录事务修改前的数据状态
- 层次：存储引擎层(InnoDB)实现
- 核心作用：实现事务的原子性(Atomicity)和MVCC(多版本并发控制)
- 事务回滚：当事务失败或主动回滚时，通过undo log将数据恢复到修改前的状态 * MVCC支持：为并发事务提供历史数据版本，实现非锁定读和一致性快照 * 崩溃恢复：系统崩溃时撤销未提交事务的修改
没有完美的方案
oracle是堆表+Undo快照，mysql是索引组织表+Undo快照， postgres是堆表+多版本
堆表方案，不用维护数据行的顺序，数据行按任意顺序排放，但是索引和数据行需要分开存储，并使用CTID来建立它们的联系。CTID就会导致MVCC时新旧元组不在同一页面的问题。
聚集索引方案，所有数据行按照主键顺序排放，主键需要是全局唯一的，这样才能保证通过主键唯一定位到数据行，达到数据行即主键索引的目的。所以InnoDB没有CTID的概念。
PostgreSQL的堆表多版本支持灵活数据模型。
综上所述，mysql InnoDB要求所有的表都必须有个主键，但是postgresql可以没有主键。
pg中FOR UPDATE和FOR NO KEY UPDATE的区别
postgres的堆表，根据ctid找到数据行的时间复杂度是多少
ctid由两部分组成：(blockid, itemid)，其中：
- blockid：表示数据所在的磁盘块（页）编号，从0开始。
- itemid：表示该块内行的索引位置，从1开始。
由于ctid直接指向数据的物理位置，其查找过程分为两步：
- 定位块：通过blockid直接访问对应的数据块，时间复杂度为 O(1)（假设块地址可通过哈希或数组索引直接映射）。
- 定位行：在块内通过itemid索引行，时间复杂度为 O(1)（块内行索引通常为固定偏移量）。
因此，理论时间复杂度为 O(1)
