pg中相关BTree部分实现了Lehman和Yao的高并发B-tree管理算法（P. Lehman and S. Yao,Efficient Locking for Concurrent Operations onB-Trees, ACM Transactions on Database Systems, Vol 6, No. 4, December 1981, pp650-670）。还用了Lanin和Shasha论文里所写的删除逻辑的简化版本（V.
Lanin and D. Shasha, A SymmetricConcurrent B-Tree Algorithm, Proceedings of 1986 Fall Joint ComputerConference, pp 380-389）。。
1先上个图，看一下函数调用过程梗概，中间略过部分细节
初始化BTree相关结构方法调用流程图
2初始化xlog相关结构
话说main()->…->PostmasterMain()->…->reset_shared() ->CreateSharedMemoryAndSemaphores()>…-> BTreeShmemInit()，调用ShmemInitStruct()，在其中调用hash_search()在哈希表索引"ShmemIndex"中查找"BTree
Vacuum State"，如果没有，就在shmemIndex中给"BTree Vacuum State"分一个HashElement和ShmemIndexEnt（entry），在其中的Entry中写上"BTreeVacuum
State"。返回ShmemInitStruct()，再调用ShmemAlloc()在共享内存上给"BTreeVacuum State"相关结构（见下面“BTree VacuumState相关结构图”）分配空间，设置entry（在这儿及ShmemIndexEnt类型变量）的成员location指向该空间，size成员记录该空间大小，最后返回BTreeShmemInit()，让BTVacInfo
*类型静态全局变量btvacinfo指向所分配内存，初始化BTVacInfo结构类型的成员值。
相关结构定义和图见下面：
typedef struct BTOneVacInfo
{
LockRelId relid; /* global identifier of an index */
BTCycleId cycleid; /* cycle ID for its active VACUUM */
} BTOneVacInfo;
typedef struct BTVacInfo
{
BTCycleId cycle_ctr; /* cycle ID most recently assigned */
int num_vacuums; /* number ofcurrently active VACUUMs */
int max_vacuums; /* allocatedlength of vacuums[] array */
BTOneVacInfo vacuums[1]; /* VARIABLE LENGTH ARRAY */
} BTVacInfo;
static BTVacInfo *btvacinfo;
初始化完BTree Vacuum State相关结构的共享内存结构图
为了精简上图，把创建shmem的哈希表索引"ShmemIndex"时创建的HCTL结构删掉了，这个结构的作用是记录创建可扩展哈希表的相关信息，不过这个结构在"ShmemIndex"创建完成后也会由于出了对象作用域而消失。增加了左边灰色底的部分，描述共享内存/shmem里各变量物理布局概览，由下往上，由低地址到高地址。图中黄色的索引项就是本节新增加的索引项。
BTreeVacuum State
相关结构图