一、B+树
数据库常用的索引结构有二叉搜索数、B树，B+树、Hash、位图和R树，其中使用最广泛的是B+树。下面简单看一下B+树的索引结构。
B+树可以看作改进的B树，在介绍B+树之前，我们先来看看B树的索引结构，如图所示，B树把各个存储块组织成一棵树的形式，这棵树总是保持平衡的，即所有叶子节点总具有相同的深度。B树中有三个节点：根节点、分支节点和叶子节点。根节点指向多个分支节点，分支节点指向叶子节点，叶子节点指向实际的数据行地址。
一棵m阶B树是一棵平衡的m路搜索树，，每个存储块（节点）存储m个关键字和m+1个指针。它或者是空树，或者是满足如下性质的树。
1、根节点至少包含两个孩子节点，即至少有两个指针被使用，每个指针指向B树的下一层存储块。
2、总是保持数据的有序性，每个存储块中的关键字按递增顺序排列。
3、分支节点至少有[(m+1)/2]个指针被使用。
4、在叶节点中最后一个指针指向它右边的下一个叶节点，即下一个关键字大于它的存储块。其它m个指针至少要有[(m+1)/2]个被使用，每一个指针指向实际的数据记录。如果第j个指针被使用，那么它指向具有该块中第j个关键字的记录。
B树的这种存储结构保证了搜索、插入和删除操作的时间复杂度在对数级别内。在搜索时从根到叶节点递归查找，将需要查找的关键字和根节点（分支节点）中的各个关键字进行了对比（可用顺序查找法或二分查找法），找到该关键字存在的区间，根据指针递归查找下一层节点，直到叶节点为止，即可找到叶节点指向的实际数据行地址。插入时，B树从最底层开始增长，当节点溢出（关键字个数多于m个）时，节点自动分裂，新节点会被提升到高一级的层数上，删除时操作正好相反。
在GBase 8s数据库中，B+树的索引每个索引节点都是双向连接的，都有指向前一个和后一个同级节点的指针，这样可以进行区间范围的查询，在同级节点间也可以进行正序和逆序搜索，大大提高了索引在数据搜索中的性能。一个节点向左或向右跳转到它的兄弟节点的能力是B+树的一个亮点，GBase 8s数据库中的所有非多维数据索引都是B+树索引。
使用B+树进行搜索时，可以对索引进行升序和降序扫描，例如：
select cname,phone from customer order by customer_num;
select customer_num from customer order by customer_num desc;
另外，再进行区间搜索时，左右搜索方式可以快速找到相邻记录的信息，B+树结构索引相对B树在区间搜索方面的性能有了较大提升，例如：
select cname,phone from customer where customer_num between 10 and 350;
select custmor_num from customer where customer_num>=10 and customer_num<=350;::: hljs-center
居中
:::
