MySQL索引的选择

Hash索引和B+树索引：

 

那为什么不使用其他的数据结构作为索引？

Hash索引：哈希表的特点就是可以快速的精确查询，但是不支持范围查询。如果做成了索引，那速度也是很慢的，要全部扫描。

平衡二叉树：

 

 

 

 1、索引也不只是在内存里面存储的，还是要落盘持久化的，如果数据多了，树高会很高，查询的成本就会随着树高的增加而增加。如果采用的是机械硬盘，效率就会更低。

2、我们磁盘读取数据是按照磁盘块来读取的，所以我们需要把数据尽量多的放在磁盘块中；二叉树一个节点只能存储一个数据，即一个磁盘块只存储一个键值对，所以不采用二叉树的模型。

 

为什么我们使用B+树而不使用B树呢？

首先我们来看看B树和B+树的结构区别；

 

B树：

 

 

 一颗m阶B树的定义如下：

1）每个结点最多有m-1个关键字。 2）根结点最少可以只有1个关键字。 3）非根结点至少有Math.ceil(m/2)-1个关键字。 4）每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。 5）所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同

在数据库中我们将B树（和B+树）作为索引结构，可以加快查询速速，此时B树中的key就表示键，而data表示了这个键对应的条目在硬盘上的逻辑地址。B树相比于二叉树而言，每个节点可以存储多个指针指向数据；故而可以减少磁盘I/O次数来提高查询效率。   B+树：

一颗m阶B+树的定义如下：

1）B+树包含2种类型的结点：内部结点（也称索引结点）和叶子结点。根结点本身即可以是内部结点，也可以是叶子结点。根结点的关键字个数最少可以只有1个。 2）B+树与B树最大的不同是内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子结点中。 3） m阶B+树表示了内部结点最多有m-1个关键字（或者说内部结点最多有m个子树），阶数m同时限制了叶子结点最多存储m-1个记录。 4）内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。 5）每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接

B+树相比于B树而言： 1、B+树的数据只存储在叶子节点中而非叶子节点只存储索引数据；我们知道索引本身也是很大的，需要以索引文件的形式存储在磁盘上，这样在索引查找的过程中可以减少磁盘 I/O的次数。 2、因为 B+ 树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的。那么 B+ 树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。而 B 树因为数据分散在各个节点，要实现这一点是很不容易的。

 

MySQL索引的选择

标签：png   nbsp   b+树   存在   链接   这一   文件的   区别   等于