B树、B+树与索引、联合索引

B树：

1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树（或B-树、B_树）。

一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：

1、根结点至少有两个子女；

2、每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；

3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：┌m/2┐ <= k <= m ；

4、所有的叶子结点都位于同一层。

在B-树中，每个结点中关键字从小到大排列，并且当该结点的孩子是非叶子结点时，该k-1个关键字正好是k个孩子包含的关键字的值域的分划。

因为叶子结点不包含关键字，所以可以把叶子结点看成在树里实际上并不存在外部结点，指向这些外部结点的指针为空，叶子结点的数目正好等于树中所包含的关键字总个数加1。

B-树中的一个包含n个关键字，n+1个指针的结点的一般形式为： （n,P0,K1,P1,K2,P2,…,Kn,Pn）

其中，Ki为关键字，K1<K2<…<Kn, Pi 是指向包括Ki到Ki+1之间的关键字的子树的指针。

应用：SQLServer数据库使用的索引数据结构，Oracle数据库使用的索引数据结构（除此之外还有bitMap位图）

B+树：一种树数据结构，通常用于数据库和操作系统的文件系统中。B+树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+树元素自底向上插入，这与二叉树恰好相反。

应用：MySQL的默认存储引擎InnoDB、MyISAM使用的都是B+树。

B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用。一棵m阶的B+树定义如下: [2]

(1)每个结点至多有m个子女； [2]

(2)除根结点外，每个结点至少有[m/2]个子女，根结点至少有两个子女； [2]

(3)有k个子女的结点必有k个关键字。 [2]

B+树的查找与B树不同，当索引部分某个结点的关键字与所查的关键字相等时，并不停止查找，应继续沿着这个关键字左边的指针向下，一直查到该关键字所在的叶子结点为止。 [2]

B树与B+树的区别：

B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于

走右结点；

B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键

字范围的子结点；

所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；

B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点

中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；

B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率

从1/2提高到2/3；

索引：

在关系数据库中，索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。索引的作用相当于图书的目录，可以根据目录中的页码快速找到所需的内容。

索引提供指向存储在表的指定列中的数据值的指针，然后根据指定的排序顺序对这些指针排序。数据库使用索引以找到特定值，然后顺指针找到包含该值的行。这样可以使对应于表的SQL语句执行得更快，可快速访问数据库表中的特定信息。

当表中有大量记录时，若要对表进行查询，第一种搜索信息方式是全表搜索，是将所有记录一一取出，和查询条件进行一一对比，然后返回满足条件的记录，这样做会消耗大量数据库系统时间，并造成大量磁盘I/O操作；第二种就是在表中建立索引，然后在索引中找到符合查询条件的索引值，最后通过保存在索引中的ROWID（相当于页码）快速找到表中对应的记录。

联合索引 ：

如果需要用到多个字段的多条件查询，可以考虑建立联合索引，一般是除第一个字段外的其它字段不经常用于条件筛选情况，比如说a,b 两个字段，如果你经常用a条件或者a+b条件去查询，而很少单独用b条件查询，那么可以建立a,b的联合索引。如果a和b都要分别经常独立的被用作查询条件，那还是建立多个单列索引。

联合索引创建方式：

CREATE [UNIQUE|FULLTEXT|SPATIAL] INDEX index_name

[USING index_type]

ON tbl_name (index_col_name,...)

index_col_name:

col_name [(length)] [ASC | DESC]

联合索引最左原则：

当使用联合索引进行查询时，查询条件必须包含索引的最左列才能有效地利用索引。这是因为联合索引的构建方式决定了索引的顺序，索引树以左边第一个字段作为非叶子节点，按照顺序进行放置。因此，如果查询条件没有包含最左列，那么索引将无法被有效地使用。这个原则的核心在于，联合索引实际上是由多个索引组成的，每个索引都包含了之前所有列。例如，如果有一个联合索引(a,b,c)，那么实际上这个索引包含了(a)、(a,b)、(a,b,c)三个索引。这意味着，当查询条件只涉及到中间的列或最后的列时，虽然索引存在，但由于不满足最左原则，因此无法有效地利用索引。

此外，最左原则还涉及到查询条件的顺序。虽然联合索引的查询条件可以交换顺序（例如，where a=1 and b=1 等价于 where b=1 and a=1），但这并不改变最左原则的应用。最常用的查询条件应该放在联合索引的最左侧，以确保索引能够被有效地利用。

总的来说，联合索引的最左原则是数据库优化查询性能的一个重要策略，通过合理地设计索引列的顺序和查询条件，可以显著提高查询效率。