数据库常用索引结构介绍
数据库常用索引介绍
索引是存在文件系统中的，是帮助MYSQL高效获取排好序的数据结构，对于索引有如下几种结构：
1 二叉树
二叉树，左孩子小于父节点，小于右孩子，父节点小于右孩子，如下图所示：
但是，二叉树可能出现单边增长的态势，会导致磁盘IO开销增大，性能低下，如下图所示
2 红黑树（jdk8 HashMap）
hash树，又叫红黑树，有自平衡的特性，如下图所示，查询6只需要4次，但是由于高度不可控，所以不用作索引
它也具有二叉树的特性，不过他能够自动进行平衡排序。
2.1 红黑树增加数据
如下图，我插入一个 39 的节点，它会先排序找到合适的位置，如下图所示
接着，40和39都为红色，需要变化位置，变换后如下图所示
接着重构45和35节点
最终如下：
2.2 删除数据
如下图所示，我删除39的节点
先找到39
然后在它的亲属节点找到与它最接近的黑色节点，然后copy它的值到 39 ，然后删除被copy的节点
因为不能出现连续的红色节点，红黑树开始自动转为平衡二叉树
删除节点相当于删除叶子节点。
3 HASH
根据一次hash计算，直接获取到对应的数据。大多数情况下不用hash。
为什么不用hash？hash类型的索引定位很快，但是不适用于范围查找，因为hash排序很慢。
4 BTREE
红黑树一个节点只能存储一个数据，BTree每一个节点可以存储很多数据行
- 度（Degree） - 节点的数据存储个数 （度中的节点会存储值） 度越大，高越小
- 叶子节点具有相同的深度
- 叶子节点的指针为空
- 叶子节点中的数据key从左到右递增
如下图所示，设置度为4，增加数据
找 5 节点 会从4到6中间找，只会查找两次。
如果度太长，会怎么设计？ cpu -> 内存 ->磁盘 内存和磁盘交互假如固定IO为4K，那么就把这个度设置为接近于4K，那么节点中的data就是多余的了，因为只要索引，为了存储更多的索引，那么需要把data从节点中删除掉，那么就引入了BTree的变种B+Tree。
5 B+Tree（MYSQL）
- 非叶子节点不存储data，只存储key，可以增大度
- 叶子节点不存储指针（因为叶子节点是查找的最终路径）
- 顺序访问指针，提高区间访问的性能
一般使用磁盘IO次数评价索引结构的优劣
预读：磁盘一般会顺序向后读取一定长度的数据（页的整数倍）放入内存
局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用
B+Tree节点的大小设为等于一个页，每次新建节点直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，就实现了一个节点的载入只需要一次IO
B+Tree的度d一般会超过100，因此h非常小（一般为3-5之间）
- 磁盘存取原理
- 寻道时间（速度慢，费时间）
- 旋转时间（速度较快）
6 MyISAM索引实现（非聚集，存储引擎是表级别的不是数据库级别的）
MyISAM索引文件和数据文件是分离的，叶子节点不是存储数据，是存储的文件指针，然后由指针指定到文件。
主键索引和非主键索引数据结构是一样的。如下图所示：
7 InnoDB索引实现（聚集，支持事务）
- 数据本身就是索引文件（按照索引把整个数据聚集起来）
- 表数据文件本身就是B+Tree组织的一个索引结构文件
- 聚集索引-叶节点包含了完整的数据记录
- 必须有主键，如果建表没有主键，表会在后台自动建立一个索引。
- 为什么非索引结构子节点存储的是主键值？（一致性和节省存储空间）
为什么InnoDB表必须有主键？并且推荐使用整型的自增主键？
如果用uuid，不用整型的话，那么每次都会在后面开辟一个空间，如果空间满了，那么就会继续向下分离，然后就会发生数据迁移，数据分裂，就会导致有磁盘碎片产生，加大开销，所以不建议用uuid。
非主键索引，建立起来的索引包含的数据是主键，优点是节省空间，减少数据一致性问题（插入数据，更新数据），加快速度，通过两次BTree索引到数据，如下图所示：
8 联合索引
对多个字段同时建立的索引(有顺序，ABC，ACB是完全不同的两种联合索引。)，一个索引相当于多个索引，
联合索引有最左匹配原则。
- 如果where条件中是OR关系，加索引不起作用。
- 需要加索引的字段，要在where条件中
- 数据量少的字段不需要加索引
最左匹配原则，eg ： key index(a, b, c),可以支持a | a,b| a,b,c 3种组合进行查找,但是不支持b,c查找
，所以最左侧字段为常量时，索引十分有效。
比如在电话本找电话，只知道名，不知道姓，找一下是非常复杂的，因为一般都是按照姓排序的，然后相同的姓再按照名来排序，所以创建联合索引应该考虑列的顺序。
ps: 通过explain sql来查看数据是否走了索引。
alert table test add INDEXsindex(aaa,bbb,ccc)#添加联合索引
9 MyISAM和Innodb的区别
- count运算的区别：MyISAM有meta-data缓存，不需要消耗太多的资源。
- 事务和崩溃后的安全恢复：Innodb提供事务，支持事务和外部键等功能，具有书屋，回滚和崩溃修复能力的事务安全型表。
- 表锁：MyISAM只支持表锁，不支持行锁，所以执行sql会自动加锁，写入时加排它锁。
- 行锁：Innodb支持，但是只有使用where的主键是有效的，非主键where都会锁全表。
- 全文检索：MyISAM支持全文检索，支持BLOB和Text的前500个字符索引。
- MyISAM适合读密集的表，Innodb适合写密集的表，读写分离的情况下，可以选择MyISAM作为读的一端。