MySQL|MySQL（一）——索引底层数据结构与算法 mysql|数据库索引|数据结构|数据

系列文章目录 MySQL（一）——索引底层数据结构与算法
MySQL（二）——Explain详情与索引最佳实践
MySQL（三）——MySQL的内部组件结构及bin-log归档
MySQL（四）——MySQL索引优化实战
MySQL（五）——MySQL索引优化实战（多表联查优化）
MySQL（六）——深入理解MySQL事务隔离级别与锁机制
MySQL（七）——深入理解MVCC与BufferPool缓存机制

索引底层数据结构与算法

系列文章目录
索引
- 索引结构为什么选择Btree或者B+ tree
- 磁盘存取原理
- - 知识扩展
  - - 打开一个word文档会经历哪些过程
    - Java程序操作（增删改查）数据库数据的简易图
    - 磁盘存取原理
- Hash
- - 描述
- B树
- - 描述
  - 特点
- B+ 树
- - 描述
  - 特点
- B树和B+树的对比
- 两种搜索引擎对比
- - MyISAM主键索引实现
  - InnoDB索引实现
  - - 主键索引（聚集索引）
    - 非主键索引（二级索引，辅助索引，也是非聚集索引）
索引最左前缀原理

索引

索引是帮助MySQL高效获取数据的排好序的数据结构
索引存储在文件里
索引结构
- 二叉树
- 红黑树
- HASH
- Btree

索引结构为什么选择Btree或者B+ tree

二叉树：平衡二叉树遇到有序的数据会退化成链表，查询效率降低
红黑树：自平衡的二叉树，虽然可以自平衡，但是在数据量较大的情况下，树的高度也会变得很大，对海量数据来说依然不是最合理的数据结构。
Hash：
- hash表只能匹配是否相等，不能实现范围查找。
- 当需要按照索引进行order by时，hash值没办法支持排序
- 当数据量很大时，hash冲突的概率也会非常大
- 组合索引可以支持部分索引查询，如(a,b,c)的组合索引，查询中只用到了a和b也可以查询的，如果使用hash表，组合索引会将几个字段合并hash，没办法支持部分索引

磁盘存取原理知识扩展

文章图片

打开一个word文档会经历哪些过程

鼠标双击word文档，这样就输入了一条指令——打开这个word文档，word文档是存储在硬盘上的，由于CPU并不能直接调用存储在硬盘上的数据
CPU收到这条指令后，会将这个word文档从硬盘读取出来，存放到RAM（内存中，所有数据都是二进制码）中
CPU再从内存中读取二进制码，“翻译二进制码”
CPU翻译结果传输到输出设备（即显示器），这时候你就能在显示器上看到这个word文档的内容了。

Java程序操作（增删改查）数据库数据的简易图

文章图片

磁盘存取原理

文章图片

寻道时间(速度慢，费时)
旋转时间(速度较快)

主要为了减少寻道时间
Hash

文章图片

描述

对索引的key进行一次hash计算就可以定位出数据存储的位置
很多时候Hash索引要比B+ 树索引更高效
仅能满足 “=”，“IN”，不支持范围查询
hash冲突问题

B树

文章图片

描述

叶节点具有相同的深度，叶节点的指针为空
所有索引元素不重复
节点中的数据索引从左到右递增排列

特点
继承了平衡二叉树的所有特点，并将其发展成多叉树，每个节点可以存储更多的数据（度）
B+ 树

文章图片

描述

非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
叶子节点包含所有索引字段
叶子节点用指针连接，提高区间访问的性能

特点
继承了B树的特点，并在其基础上进一步优化，非叶子节点只存储key，叶子节点存储所有的数据，并使用指针相连。
B树和B+树的对比对于SQL查询的性能优化，使用B树或者B+树，树的高度是由非叶子节点存放的元素决定的，非叶子节点能够存放的元素越多，高度越小。
非叶子节点存放的元素越少，高度也越大。B+树相比于B树将索引元素值全部放在了叶子节点上，使得非叶子节点的元素可以存放更多的索引key值。查询效率进一步提升
两种搜索引擎对比

文章图片

innoDB和myisam均是B+树作为索引
InnoDB是聚集索引，叶节点包含完整的数据记录，数据文件是和索引绑在一起的。myisam是非聚集索引，叶节点不包含完整的数据记录，索引和数据文件是分离的，索引保存的是数据文件的指针。
InnoDB的B+树主键索引的叶子节点就是数据文件，辅助索引的叶子节点是主键的值；MyISAM的B+树主键索引和辅助索引的叶子节点都是数据文件的地址指针。

MyISAM主键索引实现

文章图片

InnoDB索引实现
主键索引（聚集索引）

文章图片

非主键索引（二级索引，辅助索引，也是非聚集索引）

文章图片

数据文件本身就是索引文件
表数据文件本身就是按B+Tree组织的一个索引结构文件
聚集索引-叶节点包含了完整的数据记录
InnoDB表必须有主键，并且推荐使用整型的自增主键
1.如果没有主键会怎么办？
则按照下列规则来建聚簇索引，没有主键时，会用一个唯一且不为空的索引列做为主键，成为此表的聚簇索引；如果没有这样的索引，InnoDB会隐式定义一个主键来作为聚簇索引。
2.InnoDB为什么推荐使用自增ID作为主键？
答：自增ID可以保证每次插入时B+索引是从右边扩展的，可以避免B+树和频繁合并和分裂（对比使用UUID）。如果使用字符串主键和随机主键，会使得数据随机插入，效率比较差。
为什么非主键索引结构叶子节点存储的是主键值
一致性和节省存储空间
已经维护了一套主键索引+数据的B+Tree结构，如果再有其他的非主键索引的话，索引的叶子节点存储的是主键，这是为了节省空间，因为继续存数据的话，那就会导致一份数据存了多份，空间占用就会翻倍。
另一方面也是一致性的考虑，都通过主键索引来找到最终的数据，避免维护多份数据导致不一致的情况。