数据库索引模块
如何设计一个关系型数据库
程序实例：
存储管理
减少对数据的访问，提供缓存机制（全页缓存）
SQL解析
日志管理：缓存不易过大，提供淘汰策略，在数据库修改之后及时修改缓存，进行主从同步和灾难恢复
权限划分
容灾机制
索引管理
锁管理
影响数据的运行瓶颈就是IO
存储（文件系统）
索引模块
为什么使用索引
原始数据的查询方法就是将全表放入内存中，全表扫描轮询找到需要查找的数据，少量数据可以，大量数据严重影响性能。
什么样的信息能成为索引
主键：唯一键以及普通键
索引的数据结构
生成索引，建立二叉查找树进行二分查找（二叉树–平衡二叉树–红黑树）
因为是二分查找，时间复杂度为O(logn)
生成索引，建立B-Tree结构进行查找
因为添加结点导致二叉树的深度增加，虽然进行旋转可以使其继续维持平衡，但是增加了IO，降低了性能，因此提供了B-Tree结构（平衡多路查找树）。
每个结点最多有m个孩子，这个结点就是M阶B树
每个存储块包括关键字和指向结点的指针，最多有几个孩子取决于存储块的容量和数据库的相关配置
生成索引，建立B+-Tree结构进行查找
生成索引，建立Hash结构进行查找
密集索引和稀疏索引的区别
密集索引
密集索引文件中每一个搜索码值都对应一个索引值，就是叶子节点保存的不只是键值，还保存了位于同一行记录里的其他列信息，由于密集索引决定了表的物理排列顺序，一个表只有一个物理排列顺序，所以一个表只能创建一个密集索引。
稀疏索引
稀疏索引文件只为索引码的某些值建立索引项，比如InnoDB的其他索引只存了键位信息和主键，MyISAM的所有索引都是稀疏索引。
MyISAM–》 主键索引，唯一键索引，还是普通索引 —都是 稀疏索引
额外知识
InnoDB
- 若一个主键被定义，该主键则作为密集索引
- 若没有主键被定义，该表的第一个唯一非空索引则作为密集索引
- 若不满足以上条件，InnoDB内部会生成一个隐藏主键（密集索引）
- 非主键索引存储相关键位和其对应的主键值，包含两次查找
InnoDB聚簇表分布
myisam在磁盘存储上有三个文件，每个文件名以表名开头，扩展名指出文件类型。
.frm 用于存储表的定义
.MYD 用于存放数据
.MYI 用于存放表索引
可以看到—–》 Innodb索引与数据放在一起
慢查询/索引
101.数据库索引的实现(B+树介绍、和B树、R树区别)
参考文章：
数据库索引的实现原理 - 辉仔 の专栏 - 博客频道 - CSDN.NET
由浅入深理解数据库中索引的底层实现 | 学步园
102.SQL性能优化
参考文章：
高手详解SQL性能优化十条经验 - 51CTO.COM
Oracle SQL性能优化 - 一江水 - 博客园
103.数据库索引的优缺点以及什么时候数据库索引失效
参考文章：
数据库索引的作用和优点缺点以及索引的11中用法 - 技术与人生 - 博客园
正确高效使用数据库不可不知的索引失效问题 - simplefrog - 博客园
SQL优化避免索引失效 - OPEN 开发经验库
Colin Lau Oracle
哪些情况下索引会失效？ - 曾是土木人 - 博客园
