一、关于BTree

       本文我们深入学习下Postgresql的BTree索引。我们知道，BTree是一种多路平衡查找树，被广泛应用于数据库的索引之中。与我们之前接触过的最多的二叉树不同，多路树的意思是每个节点不止一个子节点。而查找树是一种顺序树，也就是说对于树种每一个节点来说，它的左子树上所有的节点都不大于它，而它的右子树上所有的节点都不小于它。由于这种特性，理论上B树查找的时间复杂度可以达到二分查找的时间复杂度O(logn)。BTree的查询效率和树的高度有关，为了降低树的高度，提高查询效率，BTree上的节点往往代表一个磁盘页，也就是包含了多个Key值。       本文我们深入学习下Postgresql的BTree索引。