MySQL Myisam引擎和Innodb引擎的区别

聚集索引、非聚集索引查询过程的比较

非聚集索引查询过程

索引和数据是分开的

1，先在索引树上找到数据的物理位置

2，到物理位置取出数据（又叫做数据回行、回表）

聚集索引查询过程

索引和数据是在一起的，在同一个文件中

聚集索引中，数据存储在主键Key索引树的叶子节点上。如果创建了其他列的索引，例如username，也会生成一颗username索引树，但是username索引树的叶子节点存主键Key，不存数据，如果就只需要username和Key属性，则取走就可以了【索引覆盖】；如果需要除username和Key之外的属性，需要拿着这个Key从上倒下走一遍主键Key索引树，走到叶子节点取走数据。

1，用主键Key查询时，找到Key的叶子节点取出数据即可。

2，用其他索引列(username)查询时，在username索引树中找到主键Key，拿着Key再走主键索引树，取走数据。如果只需要username和Key两个属性，那么在username索引树上取走就可以了【索引覆盖】。

可以做索引的数据结构有：

1，hash表

查询速度非常快，时间复杂度O(1)。hash冲突一般用链地址法解决。

最终被Pass了，原因是对范围查询效率很差，范围查询时要挨个比较。

2，二叉搜索树—>红黑树—>AVL树—>B树—>B+树

二叉排序树平均复杂度log(n)，但极端情况会退化为线性表O(n)的复杂度，导致检索性能降低。能范围查询。

红黑树和AVL树通过自旋维持平衡，红黑树有右倾问题，AVL树不存在极端情况，AVL有不错的检索性能有能范围查询，为什么Mysql没选AVL能，因为红黑树和AVL每个节点都只存一个数据，而一次磁盘IO读一个数据和读100个数据消耗的时间基本一致，那么应该尽可能在一次磁盘IO中多读一点数据到内存，尽量减少磁盘IO次数。

B树一个节点存储了多个数据，尽可能的减少了磁盘IO次数，有高效的检索速度，且支持范围查询。时间复杂度h·log(n)，h表示树高，n表示一个节点存的数据量。

B树已经不错了，但为了更高的检索性能，推出了B+树。B+树的非叶子节点存的是索引，索引比原数据小，所以一个节点中能存更多的索引，真实数据都在叶子节点，叶子节点之间用链表横向连接，支持范围查询。和B树相比，B+索引树更矮，只需很少的磁盘IO次数，大大提高了检索效率。

MySQL Myisam引擎和Innodb引擎的区别