数据库的索引的数据结构

索引是帮助数据库高效获取数据排好序的数据结构
常用的存储引擎innodb采用的是B+Tree
索引的数据结构 B+Tree （对于B-Tree的优化）
二叉树
红黑树
Hash表
B-Tree

其他数据结构的弊端
二叉树： 可能会退化成链表，会进行全表扫描，数据量大的时候，树的深度很深
红黑树：大数据下，树的深度很大，进行查找的时候进行磁盘交互次数太多

5981c50d6d3230a1fa3d9256b36e004.png

查询数据时候，先将根节点的所有数据加载到内存中，然后再内存中进行比对（索引，数据是保存再磁盘里面【存在磁盘下， 一般放在数据库安装的文件的路径的/data下面，文件一般是 表名.fm 保存数据的结构信息等。 MyISAM数据库引擎的 表名.ymd 保存数据库的数据 表名.myi保存数据库的索引，如果是innerDB引擎的话，一般是 表名.fm 表名.idb】，加载到内存进行了一次IO交互），mysql的叶节点默认大小是16kb

innerDB数据引擎与myisam引擎的区别是
innerdb 索引的叶子节点保存的是数据
myisam 索引的叶子节点保存的是数据的磁盘地址

8a5dcdf4c842c1277e3b3b9387ea3b4.png

引入概念：聚集索引
聚集索引就是索引的叶子节点包含了数据的所有数据 例如innerdb的主键索引就是聚集索引，而myisam的主键索引就是非聚集索引。

索引有两种结构，一种是B+Tree 一种是hash
一般不适用hash是因为hash 不支持范围查找（主要），出现hash碰撞（次要）

二级索引（非聚集索引）叶子节点保存的是主键，需要回表进行查找数据

6315f9c24460bc8fec2ce717d7f5b6f.png

联合索引

c58dc2901410d6fcf426322c71d4b36.png

最左前缀原则的原理就是 例：当name不是确定的情况下，age不是有序的。