【MySQL】Mysql索引优化与底层数据结构深入剖析 - 笔记
索引
使用索引，会提前存储被索引字段对应行的磁盘文件地址指针，做一次IO就能查找到数据。
二叉树
递增的索引不适合用二叉树来维护，因为递增的id会导致二叉树退化成为链表，这样建立索引的效果和不建立索引的差别不大。因此MySQL不使用二叉树做索引。
红黑树
单边增长不平衡时，红黑树会自动平衡。
JDK1.8之后，HashMap使用的就是红黑树。
在某些场景下，红黑树也会存在问题：树的高度会一直增长，数据量大的时候，还是会有很多次IO。
B树
B树是对红黑树的改造，让一个节点能够存储更多的元素。
为什么不把所有元素都加载进一个节点，放进内存中？
- 占用内存过大；一次磁盘IO有大小限制，加载不过来，会很慢
- 没有必要把一个节点搞得太大。
使用show global status like'Innodb_page_size'查看MySQL默认设置一个叶节点（页）的值：16Kb
B+树
MySQL底层使用的是B+树，是对B树的改造。
把非叶子节点的data数据都挪到了叶子结点上去存储，这样，在16kb大小固定的情况下，一个叶子节点在横向上能存放更多的索引。
例如，查找30这个元素对应的data的过程：
第一次，将15 56 77 load 进内存：
第二次，将15 20 49 load 进内存
第三次，将20 30 load 进内存，进而取出30对应的data
因此，如果添加了合适的索引，只需要进行2-3次磁盘IO，就可以找到数据。
如果不添加索引的话，需要一行一行去找，十分缓慢。
关于存储引擎
存储引擎是表级别的，不同的表可以有不同的存储引擎
主键自带主键索引。
MyISAM引擎的查询过程：
- 先去索引文件中查找指针
- 再去指针的位置磁盘中把data查询出来
数据和索引是分开存储的，它的叶子结点只存储了数据在磁盘对应文件的地址。
MySQL数据文件存储在哪里？都有哪些文件？如图：
InnoDB引擎的查询过程：
InnoDB的主键索引是聚集索引。（什么是稀疏索引？稀疏索引就是非聚集索引）.ibd文件同时存储索引和数据，以B+树的结构组织起来，在叶子节点包含了一条记录（行）的所有数据。
常见问题
为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？
MySQL InnoDB引擎设计数据默认使用B+树来组织。
如果没设置主键，MySQL会自动找一个能够作为主键的字段，作为索引去维护。
如果MySQL找不到合适的主键，MySQL会自己维护一个隐藏列，用这个隐藏列做索引。
为什么推荐使用自增的主键？
自增的主键有利于维护B+树（每次都向尾部追加），而如果不自增的话，可能会插入到B+数中间位置的某个节点中，而每个节点的大小是有限制的。超出限制后，为了保持树的平衡，会造成叶节点分裂，导致插入性能下降。
用UUID作为主键怎么样？
在B+数查找的过程需要进行多次比较大小。UUID是作为字符串存储的，而用整型数字较大小效率更高，并且整型的索引在存储的时候占用的磁盘空间更小。
用Hash作为索引怎么样？
用Hash的话，select * from t where col1 > 6这样的范围查询无法加快查询速度
而如果使用B+树，叶子结点的（双向）指针提高了范围查询的速度。
分库分表怎么办？是不是UUID更方便？
分库分表也可以使用整型。
参考雪花算法：Twitter 开源的分布式 id 生成算法。其核心思想就是：使用一个 64 bit 的 long 型的数字作为全局唯一 id。在分布式系统中的应用十分广泛，且ID 引入了时间戳，基本上保持自增的。这 64 个 bit 中，其中 1 个 bit 是不用的，然后用其中的 41 bit 作为毫秒数，用 10 bit 作为工作机器 id，12 bit 作为***。
联合索引是什么结构？
几个字段一起存储在节点汇总。排序方式：按照字段逐个进行排序，维护B+树从左到右依次递增。
使用联合索引时，注意最左前缀原则：如果a b c三列加了索引，查找时如果根据a b查找，能走索引。如果根据b c查找，无法走索引。（不能跳过某一个索引，直接用后面的索引）