索引数据结构红黑树，Hash，B+tree详解
索引是帮助MySQL高效获取数据的排好序的数据结构
没有索引的情况下，查询数据会一行行的去找，记录写在磁盘上，但是在磁盘上是随机分布的。
读取一次数据，需要与磁盘做一次IO交互，需要控制与IO的次数。
二叉树维护索引：优势，对无序字段有优势，但是对有序字段建立索引没有帮助
红黑树：平衡二叉树，也存在弊端，某些场景下对mysql索引查询效率帮助不是很大，树的高度，如果数据在叶子结点，红黑树查找数据，是从根节点开始查找，高度很高，IO次数就越多，影响效率。
优化：只要一个节点，横向多存放一些数据。就是B-Tree结构
B-Tree
叶节点具有相同的深度，叶节点的指针为空
所有元素不重复
节点中的数据索引从左到右递增排列
每个节点从左到右是有序的
16^n=2000W n是树的高度
B+Tree
非叶子节点不存储data，只存储索引（冗余），可以放更多的索引
叶子节点包含所有索引字段
叶子节点用指针链接，提高区间访问的性能。
取第一个元素，每个节点从左到右是有序的
节点所有元素都load到内存中，然后二分查找到需要的位置，找到子叶的地址
根节点（非叶子节点）常驻内存中
一个节点就是一个页：大小16K（mysql推测的最优数据），最耗费时间的是load节点，所以把节点加载到内存中比对，速度会快很多。
计算：bigint做主键占用8字节+空间地址6字节。16kb/（8+6）~1170
第一层、第二层、第三层 1170117016~2000W
一个节点存放索引的数量越多，效率越高
数据库表位置：/data/test
数据库存储引擎：引擎形容数据库表的
新建表的时候选择存储引擎
MyISAM：有三张表（user表为例）
- user.frm：数据表结构的信息
- user.MYD：数据
- user.MYI：索引
索引所在行的磁盘地址
InnoDB：整张表只有一个聚集索引
- tbox.frm：数据表结构信息
- tbox.ibd：索引+数据
聚集索引：InnoDB叶节点包含了完整的数据记录，
非聚集索引（稀疏索引）：MyISAM就是非聚集的，数据与索引两个文件分开的
查找速度：聚集索引>非聚集索引 因为非聚集索引跨表
面试题：为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？
- 主键：因为mysql设计的时候，ibd必须用B+树来组织，就可以用主键来维护索引，如果没有用主键，mysql会自动选择一个所有列都不相等的列作为索引列，如果还没有，mysql会自动创建一个隐藏列主键(rowid)。尽量减少mysql的工作。
- 主键自增：节点内的数据，是按照从小到大排列的，而且数据类型占用空间也会小，节约空间，建议整型。非自增插入数据，可能导致源树分裂进行平衡。自增的插入，尾节点追加
为什么非主键索引结构叶子节点存储的是主键值？（一致性和节省存储空间）
- 节省存储空间：如果存在多个索引，每个叶子节点没必要都存储全部数据，只要存储主键就好
- 一致性：减少复杂度，保证两个或者多个索引表里面的数据一致性。
hash结构：hash+链表
hash算法：MD5
某些情况下hash可能比B+树效率更高，但是hash存在一些缺点，不支持范围查找
B+树可以，因为叶子节点有一个指针，B+树是排好序的
联合索引的底层存储结构长啥样？
一张表不建议创建太多单值索引，建议2-3个联合索引。
索引最左前缀原理
建立索引的先后顺序进行创建，如果第一个字段就已经排好序，区分出要查找的值，就不会查找后面的字段了。如果第一个字段都相等，就对比第二个字段，一次类推
联合主键（模拟三个字段：name,age,position）三个字段不可能相等的
要用的时候一定要按照建索引的顺序去用，不能跳过第一个直接用后面的，顺序从左开始
最左前缀原理为什么要这样定义？
因为排好序索引的创建就是从左往右依次创建，最左的放第一位，第一位的是排好序的。
若有收获，就点个赞吧
0 人点赞
