索引

是帮助MySQL高效获取数据的排好序的数据结构

mysql索引数据结构为什么不适用二叉树，平衡树

1.二叉树
对于二叉搜索树而言，它的查找操作的时间复杂度就是树的高度，最理想的情况下，也就是满二叉树的情况下，查找的时间复杂度为 O(logn)。当我们在不停地动态地往树中插入数据、删除数据时，在极端情况下，二叉搜索树可能退化成链表，它的查找时间复杂度就变成了 O(n)，性能不够稳定。
2.平衡树
平衡树是在二叉查找树的基础上，增加了一条限制，左右两个子树的高度差不能超过 1，左右两边相对平衡，因此称之为平衡树。而平衡树在数据动态地删除、插入地过程中，为了维护平衡，避免树退化成链表，因此需要在删除或者插入数据后进行额外的旋转操作，会损耗一定的性能，但整体来讲，它的查找、删除、插入、更新的复杂度均为 O(logn)。它的中序遍历，数据是有序的，因此也适合范围查找。但是它的缺点是，为了维护平衡，它的旋转操作过于复杂。
3.问题
AVL 树和红黑树的增删改查性能都十分稳定，虽然中间涉及到很多旋转操作，实现过于复杂，但是还是能用代码实现出来的，只要能实现出来，这都不是事啊，性能好、够稳定就行，那为什么不用 AVL 树和红黑树去作为 MySQL 的索引数据结构呢？
答：
无论是二叉搜索树，还是 AVL 树，亦或是红黑树，它们都是二叉树的一种，特点都是每个结点最多只有两个子结点，如果存储大量数据的话，那么树的高度会非常高。而 MySQL 存储的数据最终是要落地到磁盘的，MySQL 应用程序读取数据时，需要将数据从磁盘先加载到内存后才能继续操作，所以这中间会发生磁盘 IO，而如果树太高，每遍历一层结点时，就需要从磁盘读取一次数据，也就是发生一次 IO，如果数据在树高为 20 的地方，那查找一次数据就得发生 20 次 IO，这对应用程序简直就是灾难性的，耗时太长了。因此二叉树在 MySQL 这种需要存储大量数据的场景下，是不适合当做索引的数据结构的，因为树太高，操作数据时会发生多次磁盘 IO，性能太差。
4.哈希表
哈希表对于删除、查找、更新、插入操作，都是先根据 key 计算出一个值，就能定位到数据的目标位置了，时间复杂度都是 O(1)，速度特别快。但是我们在使用 MySQL 时，经常会遇到查找某个范围内的数据，例如 between…and、>=、<=等范围查找操作。这个时候哈希表应该怎么办呢？
经过哈希函数计算出来的值就不是有序的了，所以这个时候，如果要在哈希表中进行范围查找，就只能对整个哈希表进行遍历了，只有符合条件范围的数据，才取出来。当我们数据库中的数据越来越多，达到几百万甚至几千万条的时候，这个时候，对整个表的遍历是非常耗时的。
从范围查询的场景来看，哈希表也不太适合作为 MySQL 索引的数据结构。哈希表适用于什么场景呢？适用于等值查询的场景，最经典的场景就是 NOSQL 数据库，例如我们最常用的 redis，redis 中不就是全都是 key-value 吗
B-Tree 与 B+Tree
既然二叉树因为每个结点最多只有两个子结点，最终在存储大量数据时导致树高太高，因此不适合当做 MySQL 的索引，那么让树的每个结点尽可能多的拥有多个子结点，也就是多叉树，那这样在大量储存数据时，树高就低很多了，那这样总应该可以了吧！而多叉树中典型的例子有 B-Tree 和 B+Tree。
B-Tree 的特点是无论叶子结点和非叶子结点，它都存有索引值和数据；B+Tree 的特点是只有叶子结点才会存放索引值和数据，非叶子结点只会存放索引值本身。因此对于非叶子结点，一个结点中，B+Tree 存放的索引值数量会远远大于 B-Tree（因为一个结点的空间是有限的，B-Tree 要存放索引+数据，而 B+Tree 只需要存放索引），这样就导致了每个结点中，B+Tree 能向下分出更多的叉，子结点数更多。
那么在要存储同样大小的数据文件的场景下，用 B+Tree 存储，最终树的高度会远远小于用 B-Tree 存储的高度，所以使用 B+Tree 作为 MySQL 索引的数据结构，将来在读取数据时，发生的磁盘 IO 次数会更少，性能更优，因此最终 MySQL 索引的数据结构使用的是 B+Tree。

聚集索引和非聚集索引

聚集（clustered）索引，也叫聚簇索引。

定义：数据行的物理顺序与列值（一般是主键的那一列）的逻辑顺序相同，一个表中只能拥有一个聚集索引。

非聚集（unclustered）索引。

定义：该索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同，一个表中可以拥有多个非聚集索引。

innodb（采用B+tree）使用的是聚集索引（主键）
myisam索引文件和数据文件是分离的所以是非聚集的

B-Tree ，B+Tree，Hash特点

B-Tree
•叶节点具有相同的深度，叶节点的指针为空
•所有索引元素不重复
•节点中的数据索引从左到右递增排列
B+Tree(B-Tree变种)
非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
叶子节点包含所有索引字段
叶子节点用指针连接，提高区间访问的性能
Hash
对索引的key进行一次hash计算就可以定位出数据存储的位置
很多时候Hash索引要比B+ 树索引更高效
仅能满足 “=”，“IN”，不支持范围查询
hash冲突问题

InnoDB索引实现(聚集)

•表数据文件本身就是按B+Tree组织的一个索引结构文件
•聚集索引-叶节点包含了完整的数据记录
•为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？
1、如果设置了主键，那么InnoDB会选择主键作为聚集索引、如果没有显式定义主键，则InnoDB会选择第一个不包含有NULL值的唯一索引作为主键索引、如果也没有这样的唯一索引，则InnoDB会选择内置6字节长的ROWID作为隐含的聚集索引(ROWID随着行记录的写入而主键递增)。
2、如果表使用自增主键
那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，主键的顺序按照数据记录的插入顺 序排列，自动有序。当一页写满，就会自动开辟一个新的页

3、如果使用非自增主键（如果身份证号或学号等）
由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置，此时MySQL不 得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时 又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑 的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。
4、使用整型
节约空间，相同大小的页缓存可以存放更多的索引，比较大小方便
•为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)
一致性：主键索引需要维护，二级索引也需要维护
节省空间：其他的数据只需要维护一处就可以
•为什么查询时要适配最佳左前缀原则？
联合索引的排序规则就是按照创建索引字段的顺序来进行排序，只用中间部分或者后面部分他，索引排序不规则。

索引在哪些场景下会失效？

  1. 查询条件包含or，可能导致索引失效
  2. 如何字段类型是字符串，where时一定用引号括起来，否则索引失效
  3. like通配符可能导致索引失效。
  4. 联合索引，查询时的条件列不是联合索引中的第一个列，索引失效。
  5. 在索引列上使用mysql的内置函数，索引失效。
  6. 对索引列运算（如，+、-、*、/），索引失效。
  7. 索引字段上使用（！= 或者 < >，not in）时，可能会导致索引失效。
  8. 索引字段上使用is null， is not null，可能导致索引失效。
  9. 左连接查询或者右连接查询查询关联的字段编码格式不一样，可能导致索引失效。
  10. mysql估计使用全表扫描要比使用索引快,则不使用索引。