mysql按主键排序为什么比索引快

MYSQL官方文档介绍索引是一种方便快速查询数据的数据结构。用我们生活中的例子来讲，索引就好比书的目录，如果没有目录，每次你想要查找某些内容，你必须从头开始查找，这样的效率极其低下。

索引一般比较大，所以大部分情况下索引是存在磁盘的索引文件上，也有可能是存在数据文件上。

索引的种类有很多：主键索引（这是最常见的一种索引，主键不能为空且必须唯一）、唯一索引（相对于主键索引，它的值可以为空）、全文索引（在char、varchar、text类型可以使用）、普通索引、前缀索引。按照列数来区分：单一索引、组合索引（多字段组成）

2.MYSQL索引的数据结构

在讲解MYSQL索引的数据结构之前，我们先看看了解一下其他的数据结构，看看他们的优缺点进行对比。

2.1 二叉树

二叉树简单来说就是左节点大于右节点，在理想的情况下，他的查找速度就接近与二分法的性能O(log2n)。因为在内存排序的时间是非常快的，可以忽略不计，所以总的消耗时间就取决于IO的 *** 作次数。二叉树查找速度取决树高,每次查询接口都是一次IO *** 作，也是性能的瓶颈所在。

但是也会有这种一种情况,同样也是二叉树，但是他的树非常高，导致查询一次需要多次IO *** 作，效率及其低下

2.2 平衡二叉树

平衡二叉树可以解决二叉树不稳定导致查询效率低下的缺点。平衡二叉树的特点：树的左右节点层级最高相差一层。在插入或者删除的情况下，通过左旋转或右旋转使得整个二叉树平衡，不会出现层级相差很多的情况。平衡二叉树的性能接近二分法查找O(log2n)。

平衡二叉树查找id为8的记录，只需要IO *** 作2次即可。但是仔细想一下，如果数据量很多呢？假设数据表有100W的数据，根据O(log2n)计算，大约需要20次IO *** 作。磁盘寻道大概需要10ms，总的查询时间为20 * 10 = 0.2，效率也比较低下。

还有就是平衡二叉树不支持范围查询，范围查询每次都需要从根节点遍历，效率及其低下。

2.3 B-树(改造二叉树成多叉树)

之前的几种树形结构适合与小数据量的内存查找，也叫做内查找。在1970年，R.Bayer和E.Mccreight提出了一种适合于外查找的平衡多叉树B-树。MYSQL数据文件是存在磁盘的，每次都是按照一页大小（一般而16K）读取内存。像二叉树、平衡二叉树，每次读取节点都要进行一次IO *** 作，所以树越高IO *** 作次数越多。想要提高

性能相当，mysql中区别性能的是采用哪种索引方式，而不是索引的数据类型。

mysql的btree索引和hash索引的区别

hash

索引结构的特殊性，其检索效率非常高，索引的检索可以一次定位，不像btree(b-tree)索引需要从根节点到枝节点，最后才能访问到页节点这样多次的io访问，所以

hash

索引的查询效率要远高于

btree(b-tree)

索引。

虽然

hash

索引效率高，但是

hash

索引本身由于其特殊性也带来了很多限制和弊端，主要有以下这些。

（1）hash

索引仅仅能满足=，<=>，in，is

null或者is

not

null查询，不能使用范围查询。

由于

hash

索引比较的是进行

hash

运算之后的

hash

值，所以它只能用于等值的过滤，不能用于基于范围的过滤，因为经过相应的

hash

算法处理之后的

hash

值的大小关系，并不能保证和hash运算前完全一样。

（2）hash

索引无法被用来避免数据的排序 *** 作。

由于

hash

索引中存放的是经过

hash

计算之后的

hash

值，而且hash值的大小关系并不一定和

hash

运算前的键值完全一样，所以数据库无法利用索引的数据来避免任何排序运算；

你的理解其实没啥问题。索引就是通过事先排好序，从而在查找时可以应用二分查找等高效率的算法。

一般的顺序查找，复杂度为O(n)，而二分查找复杂度为O(log2n)。当n很大时，二者的效率相差及其悬殊。

举个例子：

表中有一百万条数据，需要在其中寻找一条特定id的数据。如果顺序查找，平均需要查找50万条数据。而用二分法，至多不超过20次就能找到。二者的效率差了2.5万倍！

---