MySQL索引原理

MySQL底层索引有hash与Btree两种,其中Btree为最常用的.对此来进行细致的分析.首先提出几个问题?

• 索引的目的?

• 在数据结构中哪些可以做索引?

• MySQL索引中为什么推荐采用Btree做索引,MySQL对其是否有相应的优化?

• 一般DB建议问我们创建表时都要加主键,且这个主键推荐整形的自增长主键原理是怎么样的?

首先,我们使用索引的目的就是为了加快我们在查找表数据时的效率与速度,不然我们就要遍历表所有的内容从而查找对应的数据信息返还内容.小范围的数据查询即便不加索引也可以实现.但当今的大数据环境之下已经数据已经膨胀式增长大量数据膨胀化,所以如果不采用索引如何能实现快读定位呢那就是采用索引.

提到索引就不得不提,存储索引能的数据结构与查找数据的算法,MySQL数据库支持多种索引类型，如BTree索引，哈希索引，全文索引等等.

常见的查找算法与数据结构

• 顺序查找

• 二分查找

• 二叉树查找

• 哈希散列法(哈希表)

• 分块查找

• 平衡多路搜索树B树（B-tree）

• BTree

• 带有顺序访问指针的B+Tree

  这里选几个有代表性的算法举例(顺序/二分/hash/b树)进行解析

顺序查找,跟上文说过的问题是一样的,在大量数据下如何能快速定位即便是数据按照序列排,也不能实现快速定位,显然不可取,其复杂度取决于O(N),N为数据量.

二分查找,效率效率相对高些,但比较依赖数据的顺序排列,在有顺序的情况下,根据数据的对比找寻对应的数据范围,根据范围空间再次遍历查找,虽说高效点,但相应的 速度也至少有O(N/2)的复杂度

hash可以很高效的定位,因为hash数据存储在内存中,根据hash值可以实现快速高效的定位,可以达到O(1),但如若是范围数据,无法实现查找功能.

b树,可以实现右结点都比左边大,但可能出现一边倒情况,而且上线不明确.时间复杂度在极端情况下与顺序查找没有区别.

有没有可以实现代替的方法?采用b+树,b树不适用主要因为无法定位层级高度与数据的极端情况无法调整.故而采用b+.更为准确的说是采用带有顺序访问指针的B+Tree.

更为详细的内存容后续补充,这里只说MySQL对b+树优化的点在哪里

图-01 图-02 根据图01与 图02可以看出 ,图02相较01多了顺序指针访问,采用b+树的好处主要可以**限定层级**关系,一般MySQL层级在1-4层最好.不要小看这几个层级,也能实现上千万条数据的索引建立.一般推荐是在1-3层最好.**支持大量索引信息**为了更好理解这里说个实际的例子.

主键id，我们采用bigint，8字节,一条数据大小1KB
- 第一层
   一个页16K，每一个索引键的大小8字节（bigint）+6字节（空白块中 指针大小），因此第一层可存储16*1024/14=1170个索引键。
- 第二层
   第二层只存储索引键，能存储多少个索引键呢？1170（这么多个页，有第一层延伸的指针）*1170(每页的索引键个数，跟第一步计算一致)=1368900
   如果第二层存储数据呢？1170（这么多个页，有第一层延伸的指针）*16(16KB的页大小/1KB的数据大小)=18720，也就是能存储一万多条数。
- 第三层
   直接看三层能存储多少数据？1170*1170*16=21902400，是不是很强大，此处应该有掌声和鲜花，3次IO就可以查询到2千多万左右的数据，也就是这么大的数据量如果通过主键索引来查找是很快，这就是explain一个sql时，type=const为什么性能是最优的。

至此,上述问题,已经回答3个,剩下一般DB建议问我们创建表时都要加主键,且这个主键推荐整形的自增长主键原理是怎么样的 ,MySQL从5.5版本开始数据引擎均采用(InnDB),而这个引擎默认就采用我们讨论的b+树存储.如何根据以上内容如何快速的插入一条数据呢?显然根据b树特点,我们在第一批插入数据时结点一定是比上一个结点大的,后续内容若在不改变原有数据情况下,默认插入数据的结点都会比原来的大,这样通过找寻上一个的结点,在相应正确的位置插入即可.根据优化的关系很容易定位到具体值所在的位置,从而快实现速定位,也实现了对应数据的顺序关联.

补充额外的内容.

MySQL数据引擎主要有InnoDB与 方式也有MyISAM两种方式,两种方式分别对聚集索引与非聚集索引.

所谓的聚集索引是指像索引内容与数据等信息存储到一个文件中,而非聚集索引是分开存储的.

MyISAM的存储文件有三个，frm、MYD、MYI 文件；InnoDB的存储文件就两个，frm、ibd文件。