数据库索引B树、B+树、Hash索引

程序员小灰 - 漫画：什么是B-树？（注意查询、插入删除的图解）

程序员小灰 - 蛮会：什么是B+树？

MYSQL中的几种索引

MYSQL索引实现原理（重要）

B树与B+树

MYSQL索引原理详解

 

联合索引（复合索引）在B+树上的结构

联合索引在B+树上的结构（重要）

 

什么是全文索引？

 

数据库索引为啥要用树结构做存储？

树的查询效率高，还可以做有序。

B+树的实现细节是什么？B-树和B+树有什么区别？联合索引在B+树中如何存储？

 

索引的数据结构

索引是一种数据结构。索引本身很大，不可能全部存储在内存中，因此索引以索引表的形式存储在磁盘中。

这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

1、B+树索引

2、Hash索引

 

哈希索引就是采用一定的哈希算法，把键值换算成新的哈希值，检索时不需要类似B+树那样从根节点到叶子节点逐级查找，只需一次哈希算法即可立刻定位到相应的位置，速度非常快。

Hash 索引结构的特殊性，其检索效率非常高，索引的检索可以一次定位，不像B-Tree 索引需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问，所以 Hash 索引的查询效率要远高于 B-Tree 索引。

可能很多人又有疑问了，既然 Hash 索引的效率要比 B-Tree 高很多，为什么大家不都用 Hash 索引而还要使用 B-Tree 索引呢？任何事物都是有两面性的，Hash 索引也一样，虽然 Hash 索引效率高，但是 Hash 索引本身由于其特殊性也带来了很多限制和弊端，主要有以下这些。

 

（1）Hash 索引仅仅能满足"=",和"<=>"等值查询，不能使用范围查询。

如果是等值查询，那么哈希索引明显有绝对优势，因为只需要经过一次算法即可找到相应的键值；当然了，这个前提是，键值都是唯一的。如果键值不是唯一的，就需要先找到该键所在位置，然后再根据链表往后扫描，直到找到相应的数据；

 

由于 Hash 索引比较的是进行 Hash 运算之后的 Hash 值，所以它只能用于等值的过滤，不能用于基于范围的过滤，因为经过相应的 Hash 算法处理之后的 Hash 值的大小关系，并不能保证和Hash运算前完全一样。

 

（2）Hash 索引无法被用来避免数据的排序操作。

由于 Hash 索引中存放的是经过 Hash 计算之后的 Hash 值，而且Hash值的大小关系并不一定和 Hash 运算前的键值完全一样，所以数据库无法利用索引的数据来避免任何排序运算；

 

（3）Hash 索引不支持多列联合索引的最左匹配规则；

对于组合索引，Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值，而不是单独计算 Hash 值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash 索引也无法被利用。

 

（4）Hash 索引在任何时候都不能避免表扫描。

 

前面已经知道，Hash 索引是将索引键通过 Hash 运算之后，将 Hash运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中，由于不同索引键存在相同 Hash 值，所以即使取满足某个 Hash 键值的数据的记录条数，也无法从 Hash 索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果。

 

（5）B+树索引的关键字检索效率比较平均，不像B树那样波动幅度大，在有大量重复键值情况下，哈希索引的效率也是极低的，因为存在所谓的哈希碰撞问题。

 

 

结点度（树的度）

结点拥有的子树数称为结点的度

 

1、B-树索引

B树（Balance Tree）是一种多路平衡查找树，他的每一个节点最多包含M个孩子，M就是B树的阶。

M的大小取决于磁盘页的大小。

B-树就是B树，中间的横线不是减号，所以不要读成B减树。

 

m阶B树：

1、 树中每个结点至多有m个子结点（即M阶）； 

2、 若根结点不是叶子结点,则至少有2个子结点；

3、 除根结点和叶子结点外,其它每个结点至少有ceil(m/2)个子结点；

注：[ceil(m / 2)]个子结点（其中ceil(x)是一个取上限的函数）； 

即中间节点最少有ceil(m/2)个子结点。

4、 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息；

5、有k个子结点的非终端结点恰好包含有k-1个关键字(单节点里元素).

每个节点中元素个数n必须满足： [ceil(m / 2)-1]<= n <= m-1。(即M阶树单节点最多有M-1个元素)

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

 

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

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

       a)   Ki (i=1...n)为关键字，且关键字按顺序升序排序K(i-1)< Ki。 

       b)   Pi为指向子树根的接点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。 

       c)   关键字的个数n必须满足： [ceil(m / 2)-1]<= n <= m-1。

 

 

整理后：

m阶：

每个结点至多有m个子结点

根结点至少有2个子结点

中间节点至少有ceil(m/2)个子结点

所有叶子结点都出现在同一层

单节点最多有m-1个元素,一个节点的子节点数量会比元素个数多1

 

根二中C元减1

 

三阶B-树：

 卫星数据：

指的是索引元素所指向的数据记录。比如数据库中的某一行。

B树中无论中间节点还是叶子节点都带有卫星数据。

B+树中，只有叶子节点带卫星数据，其他中间节点仅仅是索引，没有数据关联。

 

 

2、B+树索引

MYSQL使用B+树做索引。

 

三阶B+树：

 

一个m阶的B+树具有如下几个特征：

1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

3.每个父节点的元素都同时存在于子节点中，是子节点中的最大（或最小）元素。

 

根节点的最大元素是整个B+树的最大元素。

由于父节点的元素都包含在子节点，因此所有叶子节点包括了全部的元素信息。

每个叶子节点都带有指向下一个节点的指针，形成一个有序链表。

 

B+树的好处主要体现在查询性能上：

单行查询：

B+树会自顶向下逐层查找节点，最终找到匹配的叶子节点。

看起来跟B-树差不多，但其实有两点差别：

1、B+树中间节点没有卫星数据，所以同样大小的磁盘页上可以容纳更多节点元素。

这就意味着，数据量相同的情况下，B+树结构比B-树更加矮胖，因此查询时IO会更少。

 

2、B+树的查询必须最终找到叶子节点，而B-树只需要找到匹配的元素即可，无论匹配元素是中间节点还是叶子节点。

因此B-树的查找性能不稳定（最好情况是只查根节点，最坏查到叶子节点），而B+树每次查找都是稳定点 。

 

范围查询：

B-树只能依靠繁琐的中序遍历，而B+树只需要在链表上遍历即可。

 

 

综合起来，B+树比B-树优势有三个：

1、IO次数更少

2、查询性能稳定

3、范围查询简便。

 

=====================================================================================

MYSQL索引实现

在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的，本文主要讨论MyISAM和InnoDB两个存储引擎(MySQL数据库MyISAM和InnoDB存储引擎的比较)的索引实现方式。

 

MyISAM索引实现

 

MyISAM引擎使用B+Tree作为索引结构，叶结点的data域存放的是数据记录的地址。下面是MyISAM索引的原理图：

 

这里设表一共有三列，假设我们以Col1为主键，则上图是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：

 

同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

 

注意：

主索引和辅助索引都是B+树，叶子节点都存储的是数据记录的地址，索引文件和数据文件是分离的，主索引和辅助索引都不会影响数据文件。

 

 

InnoDB索引实现

虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。

  

第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶结点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

 

上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶结点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

  

第二个与MyISAM索引的不同是 InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，下图为定义在Col3上的一个辅助索引：

 

这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

  

了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

 

========================================================================================

联合索引（复合索引）在B+树上的结构

联合索引在B+树上的结构（重要）