PG的Btree索引来自2篇文章

• 《Efficient Locking for Concurrent Operations on B-Trees》
• 《A Symmetric Concurrent B-Tree Algorithm》

LY算法

• 每个page增加2个机制

• • right-link：每个page指向右节点
  • high-value：这个page所有子节点中的upper-bond

• 搜索过程无锁：

• • 通过一个downlink达到一个child page
  • 用这个page的high value和search key进行比较
  • 如果search key比high value还要小，则目标值还在这个page中，这个page没有发生分裂（或者发生了分裂，在它的父page中得到了体现，否则就不会顺着这个downlink下来）；
  • 如果search key比high value还要大（正常情况是小于），那么说明，在父page中查找downlink的时候，这个page一定发生了分裂，并且没有在父page中更新，才会顺着错误的downlink下来，此时需要通过right-link查找右边的page，也许在通过downlink查找时发生了多次分裂，因此需要一直往右查找；

• 读锁：虽然搜索过程是无需上锁的，但是但是在读取一个page的时候，需要上读锁，防止过程中被其他进程修改；

PostgreSQL对LY的修改

• 键值的唯一性
• 锁

• • page在共享内存中，可以被多个进程看到。和LY论文中，假设page是在每个进程内的一个copy，不被共享；
  • LY无需上锁；
  • PG需要读锁，防止读的过程被更改
  • 缺点：降低了并发读
  • 优点：读锁提升为写锁后，无需再次re-read 页面。上了一个读锁+pin锁，保证page的内容是最新的；

• 树的scan

• • 插入、删除、更新会用到scan；
  • right-sibling支持向右顺序扫描；
  • 比LY新增left sibling，支持向左扫描；
  • 分裂算法比LY需要额外维护：
  • 对当前正在分裂的page上锁；
  • 对当前正在分裂page的右page上锁，因为这个右page的left-sibling需要指向新分裂出来的page，因此也需要更新；
  • 即使同时对分裂的page和它的右page上锁，向左顺序扫描时：
  • 进程P1：当通过一个page-A的left-sibling得到了它的左边的page-B指针；
  • 进程P2：对这个page-B进行了分裂；
  • 进程P1：需要对这个page向右seek，直到通过一个page的right-sibling看到了page-A，那这个page才是真正的page-A左边的一个page；
  • 引入删除后，更加复杂；

• 锁的粒度

• • 只上一次读锁
  • 只有在scan一个page的时候上读锁，为了尽量减少上锁的次数
  • 在解析叶子节点时一次读取所有符合条件的items，拷贝tid到自己的内存中
  • 后续直接处理tid，无锁再对这个索引页上锁；
  • pin锁
  • 读取完一个page之后，会释放读锁；
  • 持续加pin锁，为了保护并发deletion

• • • 一直向右查找，一直上pin锁
    • scan过程最终停止的时候，在一个被上了pin锁的右边
    • 对于并发的插入和page分裂是安全的：items的移动不会跨越多于一个page边界，只会从一个page移动到下一个page，而不会跳过右边的邻居page；
    • A->B
    • 在scan索引页面A时，同时得到了它的next为B，也即是下一个扫描的页面；
    • 当把A扫描完了之后，A发生了分裂 A' -> C -> B
    • 部分item转移到了页面C上，不会转移到页面B上（不跨越page边界）
    • 新分裂的页面C不会被扫描（否则会重复），而是直接扫描页面B
    • 可以保证：scan的时候不会miss任何item，也会re-scan任何items

• • 在解析一个page内容的时候，需要记住它的next指针

• • • 因为当前这个page可能会split
    • 如果在split之后，再去取next指针，那么它的next指向的就是新分裂出来的
    • 分split出来的page的内容已经处理过了，出现了re-scan

• • 一些场景需要先对next page上锁，再释放当前page的锁，在向右和向上是安全的；向左和向下会导致死锁；

• root page的分裂

• • LY没有讨论root page满的场景
  • PG的算法是：
  • root page的split和正常的page相同；
  • 构造一个新的root page，指向这两个page；
  • 新的rootpage会被install到meta-data page中；
  • 搜索的时候：

• • • 读取到的meta中指向的root是新的root，这个root没有右指针，直接解析这个root即可；
    • 读取到的meta中指向的root是老的root，这个root是有右指针，会继续往右边查找；

• • 递归向上插入
  • 在插入开始时候会记录从root到叶子节点的backtrace路径
  • 当叶子节点split之后，需要一直往上层父节点插入对新page的指针
  • 如果找到了路径的头部root（老的root），仍然需要往上插入时，没有保存后续新root的指针
  • 解决：从meta-data重新搜索一次路径

• • • 通常情况只会分裂一次，只需要读取meta-data，和新的root就可以了（新root指向了老的root）
    • 不排除，root被分裂了多次，那么可能这条新root到老root之间的路径会比较长了

• key的长度

• • LY假设key的长度是定长，因此会有一个page能存item的上限
  • PG要处理变长的key
  • 在page split的时候，尽量在2个page上分散均匀的字节数，而不是item数目
  • 要考虑正在插入的item长度，否则分裂之后的2个page可能没有空间存储新的item

Deletion算法

• super-x锁

• • 在删除一个leaf item时，需要上super-x锁，保证没有其他backend进程持有该page的pin锁；
  • 理论上btree索引本身的正确性是不需要super-x锁的，因为index scan逻辑上只会在pages之间停留；
  • 上supler-x锁的原因是：在non-full vacuum和index scan之间保持interlock
  • vacuum先delete索引项，再回收heap表的行指针；
  • super-x保证vacuum不能回收该索引page，这个索引page正在被其他backend进程执行indexscan（已经把内容读取到了自己的buffer中），并正在进行回表，如果此时vacuum进行工作，删除了索引项，并且去删除了heap行指针，那么这个行指针可能会被立即reuse，指向的行已经发生了变化；

• • • 必须维护索引项和行指针是对应的，这个一一对应的关系需要锁保护，因此，vacuum在清理一个索引页时必须等待其他进程退出；

• • super-x机制只对indexscan同步的访问heap表有效，对bitmap scan无效；
  • 只有在non-mvcc时才需要super-x锁，在mvcc中，vacuum回收了行指针，heap表中的行指针被使用其他无关的tuple占用了（一定是一个后面的进程进行了插入），对当前后端进程进行的indexscan回表时，是不可见的。
  • 因此，在使用mvcc时，并没有其他因素证明：上了S锁读取了page内容后，不再上pin锁是错误的（尽管是上了pin锁。当前是上了pin锁的，就是为了告知vacuum：‘当前有人在访问这个索引页，不能进行回收’）
  • 当前在indexscan时上了S锁并读取了索引页的内容后，仍然需要pin锁的原因是：
  • btree是non WAL-logger的；
  • 当前scan是index-only scan；
  • 如果PG社区后续优化了btree，使得所有情况都不要pin锁，那么vacuum的流程会简化，super-x锁的机制也就不再需要了；

• btbulkdelete

• • pin锁并非始终会上，另外即使上了pin锁，在spilt之后，一个backend进程之前indexscan读取到的items，也已经split到了右边的某个page上去了；
  • vacuum为了保证会提前删除被indexscan看到的item指向的heap tuple，需要上btbulkdelete锁：对所有的叶子节点上super-x锁，即使这个叶子page没有包含任何需要删除的tuple；
  • backend-A进程indexscan了一个TID，该TID被回收了并且被其他后续backend-B进程写入其他内容，会导致A进程结果集出错；
  • 必须持有所有index page的pin锁，直到该进程看到的所有index items对应的heap tuple被读取上来；
  • 只要有进程indexscan持有了deleted tuple的一个TID拷贝（读取了叶子page中的item），btbulkdelete就不能返回；

• internal索引页

• • 中间索引页中删除items时，没有任何锁操作，因为backend进程从root往下descend时，路径上page没有上任何的锁和pin锁；
  • 因此，当backend进程通过stack往上ascend时，可能要找的stack中存放的item在该iterm的右边（永远不可能出现在左边，分裂是往右发展的，合并也是把右边的pagemerge到左边的page上，因此原来的item指向的page要么包含该item，要么在它的右边page包含item）；
  • 在re-found到父节点前，会一直对lower page上锁。因此，能够保证父节点page一直存在，且没有被删除；（原因是：父节点page删除的条件是它只有一个child页面，而且这个child页面也是要删除的，只要保证底层的页面不被删除，父页面就一直在）
  • 另外，通过匹配downlink的page number而不是keys，因此在识别parent item时不会出现‘misidentifying’;

page delete算法

• 删除page从叶子节点开始

• • 只会从btree中删除完全空items的page；半满的page进行合并会更好的利用空间，但是无论是把items往左还是往右merge，都会使得反方向的scan扫描不到部分item；
  • 永远不会删除一个level中的rightmost页面，这个限制用来简化遍历的算法；
  • page的删除永远是从空的leaf page开始触发的，中间节点page的删除只能发生在，删除一个叶子page的branch leading的途中，并且这个中间节点只有一个child，而且这个child也要被删除；

• 删除page的two-stage，stage1过程

• • 被删除的page从parent节点中摘除掉，同时标记该page为half-dead；
  • 在通过该page查找parent page时，过程和insert过程查找parent page一样的：通过stack中的page指针找到parent page，同时尝试move right。因为parent page可能发生过split；
  • 对目标page和parent page上锁，修改target page的downlink指向右sibling，同时移除它的老的downlink（这里是指移除老的downlink page吗？）

• • • 效果：使得target的key space立即属于右邻居节点了，此时，左邻居节点和右邻居节点都不需要修改‘highvalue’，因此也就不存在因为更新‘highvalue’而导致的左右邻居节点的空间不足的问题；

• • 同时，标记target page为half-dead，后续的search会跳过half-dead的page，向右移动（如果是逆序scan的话会向左移动）；
  • 最终：使得该page达到类似split的状态：这个page没有downlink指向它，仍然连接指向它的右节点；
  • 注意：Lanin和Shasha的论文中，倾向于把key space往左边移动，因为论文中的假设中没有左指针，pg的实现有左指针，因此简化处理；

• 不允许跨parent合并

• • 不能把key space合并到右邻居，除非右邻居和它是在同一个parent节点下面
  • 原因是：如果把最右侧的page的key space合入到了右邻居节点，那么它的parent的key space就缩小了，而它parent的右邻居就扩大了，那么需要相应的更新父节点，和父节点的右邻居。最糟糕的情况是：更新所有到root节点的page；
  • 该过程不能原子性，同时性能也会退化
  • 一个parent页面的rightmost不会被删除，除非：它是唯一的一个child page，并且这个page的parent也会被删除；

• 删除page的two-stage，stage2过程

• • 被标记为half-dead的page从它的左右邻居节点中摘除掉
  • 对左邻居上锁，target上锁，右邻居上锁
  • 更新左邻居指向新的右邻居，右邻居指向新的左邻居
  • 更新target page为deleted状态；

• 移除最后一个child节点

• • 父节点也要移除
  • 该叶子节点是parent节点最后一个child了；
  • 改叶子节点移除了，parent节点也要移除；
  • stage1：因为叶子节点和父节点都要删除，更新祖父节点，移除指向父节点的downlink，如果祖父节点也只有最后一个child节点了，那么就一直往上找，直到拥有2个以上child的page，然后移除downlink；
  • 此时，叶子节点已经被标记为half-dead了，某个拥有2个child节点的祖先节点中指向的downlink被移除，该被移除downlink节点的block number被存放在该叶子节点上；
  • 这样，就保存了一串page，通过downlink一直能找到叶子节点，而头指针保存在了叶子节点中；
  • 在递归的往上找大于2个child的page过程中，对中间节点无需上锁，因为：

• • • 此时的中间节点不可能产生split（也不可能被delete，因为当前就是delete的流程中）
    • split只能由于子page产生split，而叶子page已经上锁，并标记为half-dead，不可能split；
    • 因此，无需对中间节点上锁；

• • 删除指向to-be-deleted chain的祖先节点的downlink，可以高效的把其所有子节点的key space转移到右邻居中，而且这个过程是原子的（从上层转移key space）。当然，仍然有可能存在并发scan的进程访问到中间节点，它会在达到叶子节点时，发现叶子节点是half-dead状态，一直向右移动直到发现正确的page；
  • stage2：
  • to-be-deleted chain中的topmost节点从它的左右邻居节点剔除掉，同时half-dead叶子节点更为为下一个topmost节点；
  • 一直循环到叶子节点本身也从左右邻居踢掉了；

• 一个deleted状态的page（经历了2阶段删除）不能被立即回收，因为可能存在其他进程正在等待这个page（删除进程先发生，其他进程对这个page上S锁时发生等待。可能是从parent节点的downlink过来的，也可能是左右邻居节点过来的）。这些进程在获得锁之后会看到这个page是dead状态，scan过程需要一直往左或者往右直到找到了一个non-dead的page，这个page拥有了那些被删除page的key空间

move-left算法

• 复杂性来自2方面

1. 1. 1. 左邻居发生了split，在它右边产生了一个新的page，必须找到它左边节点（被一个scan进程看到的left sibling指针）分裂出来的一系列节点中的最右边；
      2. 当前正在处理的page是deleted了，它根本就不在sibling chain上；

• 算法

1. 1. 1. 记录当前所在的page为‘original page’；
      2. 往left-link移动一次（如果left-link为空，则整体流程退出）；
      3. 开始向右遍历找所有活者的page，它的right-link等于‘original page’，如果找到则退出；
      4. 原则上，可以一直往右遍历直到末尾
      5. 实践中，最好在重试几次都失败后退出流程。不太可能：在当前进程持有的‘original page’原来的左节点split了太多的次数，以至于一直往右遍历太多次数找不到了；如果遍历了太多的次数没有找到，那么‘original page’被delete了（需要重试，因为它已经不在chain中了）；
      6. 返回到‘original page’：
      7. 如果它还活着，则返回到第1步（3中猜测它是dead的page是错误的）；
      8. 如果它dead的，则一直往右找一个non-dead的page（由于righmost不会被删除，因此必然能找到），那么这个page就做为新的‘original page’（原来的original page被delete了，它的key space被合并到了右边），从第1步重新开始；

• • • • 当停在一个livepage上时，它的左侧的keyspace boundary和之前的左侧的keyspace boundary是相等的，只不过这个新的livepage的左指针在chain中，可以正常的move left；

page回收

• 删除index page中的一个item需要super-x，保证当前没有进程引用这个page，防止进程之前已经读取到local buf的TID被重用了；
• 它和回收page的差别是：其他进程可能通过左右邻居节点得知了该page，后面会进入到这个page的操作上

• • 如果是删除item操作，会上S锁，然后读取最新的内容（原来的page还在只不过内容变了）；
  • 如果是回收page操作，这个page在该进程scan过程中被标记为了dead，然后被回收消失了，那该进程进入到这个page上的行为无法确定（page不在了）；

• 被delete的page只有在没有进程scan引用到它时（或者即将被引用）才能被回收，在此之前它必须保持在原来的page位置，它的左右page引用不到它，而它自己的左右指针仍然指向它被delelte之前的位置（move left时还会向右一直找一个non-dead的page）；
• 实现：等待所有活跃事务退出；

• • 这是一个充分不必要条件；
  • 当page被标记为dead时，page上记录next-transaction counter value；
  • vacuum可以回收该page，如果该事务ID比RecentGlobalXmin小（说明page被标记为dead时的活跃事物都已经退出，新的事务也不会引用到该deadpage）；
  • 副作用
  • 等待没有Snapshot的事务XID；
  • 必须等待到有一个新的事务被分配，而且commit了；

• 回收page的动作仅仅是在fsm中记录，该page的内容会被下次split复用时重写；如果发现一个deletepage的事务号非常老，需要标记为FrozenTransactionId，防止回卷）；

fast root

• 由于永远不删除任何层次的rightmost节点（也就永远不会删除root），树的高度就不会减小；
• 当进行大量的删除后，树的root下面可能会连续出现几个层级，都只包含一个page，影响后续的descend性能；
• Lanin and Shasha：维护一个fast root指针，指向最底层的single-page；meta-data中维护fast-root和真正的root两个指针；scan从fast-root开始；

• • 当发生split或者delete需要调整fast-root
  • split：当原子的在父节点插入时调整fast-root；
  • delete：当原子的更新delete page时；
  • 在split和delete流程中更新fast-root避免了锁竞争；

vacuum扫描

• vacuume需要线性的扫表btree，找到可以回收的deleted page，满足：被标记为dead时的xid比当前活跃事务列表要老。在这个遍历过程中，同时找到deletable tuples；
• 8.2之前btbulkdelete通过index顺序扫描叶子节点，可以通过物理page号从0开始顺序遍历，需要处理在并发的split时可能错过部分标记deleted tuples：

• • spli时可能把部分tuple移动到了比vacuum已经扫描过的更靠前page number的page中（index order不存在这个问题，btree的完整性保证）；

• vaccum cycle ID机制

• • 该机制可以发现自从vacuum启动之时，是否发生过split（因为之前的split出来的page会被物理顺序扫描到）；
  • 如果vacuum物理顺序扫描page时，发现这个page刚刚发生了分裂，而且分裂出来的新page是在page number更小的page范围中
  • vacuum的顺序扫描暂停，沿着right-link先去处理该分裂出来的page，需要一直right link多次（多次分裂），直到遇到一个page，它是在vacuum启动前分裂出来的，或者新分裂出来的page是大于当前vacuum的扫描点；
  • 然后，再返回顺序扫描；
  • 这个机制保证所有的tuple都会被visit到，但是可能会visit2次（比如刚刚分裂到左边的page，又发生了分离到了右边），但是不会有不好的影响；
  • 另外，该机制也能处理对于’是否刚刚分裂‘的测试的返回错误的判断，只要不总是返回错误的结果就行；
  • 实现：通过测试每个index page上一个比较的小的计数器；

Fastpath For Index Insertion

• 插入的数据已经是按照index key排好序的
• 如果上次插入的page是最右侧的apge，缓存这个page。下次插入的时候直接使用这个page，并进行校验是否应该插入到这个page。可以避免从root再次的walk down；
• 这个优化能work的的一个前提是：只有一个non-ignorable 最右侧的叶子节点，RecentGlobalXmin。
• 使用这个cache page做为hint，始终是有效的page，因为B-Tree中有一个这样的page
• 可能这个page被删除和回收了，cache page就会被检测为invalid，但是只会发生在恰巧这个page被回收，后续再次做为rightmost被回收

On-the-Fly Deletion Of Index Tuples

• 进程在查完btree后，回表查找heap时，发现该heap是dead并且是可移除的（对所有活跃事务来说该tuple是dead的），可以在index entry中标记为’known dead‘，后续的indexscan跳过该heap tuple。

• • 通过标记index item中的lp_flags为LP_DEAD；
  • 该功能不适用于bitmap scan，因为只有常规的indexscan访问index和heap是同步的方式，bitmap没有好的代码点来做这个标记；

• 一旦一个indextuple被标记LP_DEAD就可以立即从btree中删除了，由于index scan只会在page之间停留（一次读取完page所有tuple），并不能使得这些已经读取了该索引page的进程丢掉这个index tuple（被读取到自己的buffer中了）

• • 允许在只持有S锁的情况下更新LP_DEAD，并不能保证更新成功，就像heap tuple一样做为hint使用。因此，此时也不能物理删除该tuple(上的是S锁，也不能成功的更新lp_dead)；
  • 物理移除需要上x锁，在当前的实现中，发生在page split时，顺便移除标记为LP_DEAD的tuple；

• 在物理split的时候移除了dead tuple，导致heap上dead tuple没有index entry指向它，对当前的VACUUM没有影响。另外，REINDEX也会造成同样的状态，因为它会跳过dead 的tuple；
• 删除LP_DEAD的item只需要上x锁，不需要super-x锁。看起来好像打破了vacuum和indexscan之间的锁关系（只有当pin=1，才会触发vacuum，因为可能有其他indexscan持有该page的TID）

• • 只要有indexscan进程对它所拥有的index item所在page持有pin，vacuum在执行btbulkdelete时就会等待（需要super-x，等待有所indexscan退出），因此就不会删除heap tuple。因此仅仅是从index page中把这个dead tuple移除了，heap tuple上还有，其他indexscan进程已经读取到local buffer对这个dead index tuple的引用仍然能够访问到heap上；
  • 这也是btbulkdelete需要对所有的叶子page上super-x，而不只是它正在处理的page；
  • 因此，可以处理在释放pin锁之后对indextuple标记LP_DEAD的场景
  • 在读取index page时记录此时的LSN
  • 如果整个indexscan期间没有上pin锁，同时LSN也发生了变化（有新的entry插入或者发生了split，进行了清理），就不标记；

WAL Considerations

• 当发生crash时，插入和删除算法并不能保证btree的一致性，为了提高健壮性需要依赖wal的回放

• • 一个wal entry是atomic action

• 叶子page没有split

• • leaf page上插入item（没有触发split）和leaf-item的删除操作（叶子page称为空页后续被删除页面是另一个动作）都是单条wal entry；

• 插入导致split

• • 第1条WAL：记录在插入层发生的事件，自身的变化以及右邻居需要更新它的left-link；
  • 第2条WAL：parent level的插入操作，同理，父节点也可能导致split；

• root split事件：WAL entry记录’new root‘，而不是’insertion‘；
• 由于split有2个原子的操作（水平方向和垂直方向），可能在split page和插入downlink之间crash，在recovery之后，新page的downlink丢失。indexscan可以根据rightlink正确的查找到没有downlink的新page，2个问题：

• • 如果缺失downlink的page多了，影响查询性能；
  • 如果缺失downlink的page再次发生了分裂，那这个新的page在父节点层就没有地方插入了（它的左边节点没有再父节点插入，因此它的右边节点在父节点无法插入，如果强行插入，就会使得它左边没有downlink的page的keyspace属于了右边，搜索的时候通过父节点先进入右边的page，就无法找到左边的page了，因为searchkey符合highvalue的要求，另外btree的分裂往右进行，因此只往右查找）

• 补齐downlink的做法是：当insert时，进行定位的过程中；

• • 理论上也可以在search的时候补齐downlink，但是在一个read-only的操作中进行更改btree的状态和直觉不符合（standby也不允许写）
  • 看起来在执行vacuum的过程时补齐downlink比较合理，但是vacuum本身是为了回收空间，如果在vacuum执行的时候磁盘的空闲空间不多了，本来期望vacuum释放出更多的空间，如果补齐downlink在parent层插入指针，会导致一系列的split和new page，可能会导致磁盘空间耗尽。而insert可以扩展物理空间；

• INCOMPLETE_SPLIT（分裂中）

• • 为了方便的识别出缺失的downlinks，page在发生split时，在原来左边的page上标记INCOMPLETE_SPLIT，当downlink成功的插入了parent层，则清空改标记；
  • 成功的插入了父节点并且清空了子节点上的标记后，child节点才会释放锁，在这之前一直处于上锁状态，为了保证分裂中的page不被其他进程看到，如果触发了父节点发生了split，则需要操作祖父节点，该child的锁可以立即释放（因为父节点已经成功的插入了）；
  • 实际上只要左child page顺利的分裂出了新的page，就能够被indexscan到，但是如果此时新产生的page又发生了分裂，它左边的page没有在父节点插入成功，它也无法在父节点插入，因此还不如把子节点上锁，让它不可见，反正更新父节点是很短暂的内存操作。另外，其他进程可能在刚刚要发生分裂时，desend到了这个page，然后分裂操作开始先上了x锁，另一个进程等待，获得S锁后，仍然需要move right；
  • 在给左边page标记INCOMPLETE_SPLIT时，如果左边page也是一个’缺失downlink的right page‘，因为这样只需要通过该page的INCOMPLETE_SPLIT标记就能知道是否需要在parent中插入右边page的downlink了；

• 当split一个非root的page，分裂动作的WAL在它自己的层次完成，如果影响了fastroot（split导致该层的page数多于1，fastroot需要向上移动），对metadata中fastroot的修改放到parent层次中的WAL中。当root分裂时，metapage的修改做为’new root‘的一部分，而不是单独的；
• page delete的每个step都有对应的WAL

• • 第1条WAL：标记leaf page为dead状态，移除downlink；
  • 第2条WAL：水平方向unlink这个page；
  • 如果出现crash或者vacuum异常退出了，btree的性质保证了依然能够保持一致性的状态。后续的vacuum还会发现half-dead的叶子page继续完成删除操作；

• 在9.4之前没有完成的分裂和删除是在recovery过程完成的，而不是像现在lazy的在insert和vacuum完成。前者会导致recovery复杂度上升，并且使得nbtree的修复只有在recovery才会触发。另外，split也会在recovery中发生，此时如果出现磁盘满（对parent进行插入）或者内存满又会导致新的incomplete split出现；

Scans during Recovery

• btree索引的性质支持在recovery过程中仍然能够被使用；
• 在recovery过程中，只有一个writer和多个reader；

• • 因此上锁的限制可以放松，在block split过程中不再需要上两个锁
  • 在父page中插入downlink时，子page也会被上锁，阻止在对parent中插入成功之前，new page和子page对外是不可见的，防止再次分裂时父page没法插入；
  • WAL记录了在split的过程中对每个层的修改和上锁顺序，每个修改上适当的锁，保证并发读是正确的（btree是一致的）；
  • 也可能reader过程过程中出现page的split，只需要right-link；

• 在recovery过程中indexscan，ignore_killed_tuples和kill_prior_tuple设置为false，因为oldest xmin在standby上比master小，也就是tuples可能在mastert上被标记为killed，而standby上仍然能见。WAL中不记录tuple被标记为killed，由于full page writes，它仍然在standby上出现；
• 需要支持再recovery期间的scan，要在recovery结束后开始正常服务时退出，因为standby在被promote时会进入正常服务状态
• 在strandby上对non-mvcc的scan无需上锁

Other Things That Are Handy to Know

• 每个nbtree的第0个page是meta page，存储了root page和fast-root；
• 在index的relcache entry（rd_amcache)中缓存了metapae；
• 进程A在从rd_amcache中读取了之后，可能会其他进程修改，那么进程A就读取到了老的meta信息

• • 如果是访问root page，可以通过校验is-root标记；
  • 如果是访问fast root，可以通过校验是否有其他siblings；

• nbtree的一个index页必须能存放下至少3个item：1个highvalue，2个real data items；
• ScanKey结构2种用途：search和insert
• pivot index tuple

• • 不指向heap tuple，只用来tree的遍历；
  • 语义是：中间page表明全部tuple，叶子page表明high keys；
  • 作用：表达key space属于page哪个部分，可以从deletd/killed的tuple上构造而来；
  • suffix truncation：在页面split时，对highkey key进行截断，因为highkey只是用来表明上界；

• suffix truncation优化

• • 在page 分裂过程中，左边page的high key tuple，可以省略部分，只要能表达high的语义就可以了；

Notes About Data Representation

• 左右指针存在Opaque区域汇中，位于每个page的最后面；
• 叶子节点level=0，一直往上增加，root节点为高度-1；
• highkey位置

• • 非rightmost，hightkey存放在第一个item位置，data item从第2个开始；
  • rightmost，没有highkey，data item从第1个开始；

• 叶子page上的data items指向TID和相关key的值；
• 非叶子page上

• • data items是指向child page的downlink；
  • data item的每个key是在downlink的左边，也就是它指向child page的下边界，high key是上边界；