索引底层数据结构与算法
- 索引
- 索引结构为什么选择Btree或者B+ tree
- 磁盘存取原理
- 知识扩展
- 打开一个word文档会经历哪些过程
- Java程序操作（增删改查）数据库数据的简易图
- 磁盘存取原理
- 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程序操作（增删改查）数据库数据的简易图
磁盘存取原理
- 寻道时间(速度慢，费时)
- 旋转时间(速度较快)
主要为了减少寻道时间
B树
描述
- 度(Degree)-节点的数据存储个数
- 叶节点具有相同的深度
- 叶节点的指针为空
- 节点中的数据key从左到右递增排列
特点
继承了平衡二叉树的所有特点，并将其发展成多叉树，每个节点可以存储更多的数据（度）
B+ 树
描述
- 非叶子节点不存储data，只存储key，可以增大度
- 叶子节点存储指针
- 顺序访问指针，提高区间访问的性能
特点
继承了B树的特点，并在其基础上进一步优化，非叶子节点只存储key，叶子节点存储所有的数据，并使用指针相连。
两种搜索引擎在索引上的对比
- InnoDB是聚集索引，使用B+Tree作为索引结构，数据文件是和（主键）索引绑在一起的（表数据文件本身就是按B+Tree组织的一个索引结构），必须要有主键，通过主键索引效率很高。但是辅助索引需要两次查询，先查询到主键，然后再通过主键查询到数据。因此，主键不应该过大，因为主键太大，其他索引也都会很大。MyISAM是非聚集索引，也是使用B+Tree作为索引结构，索引和数据文件是分离的，索引保存的是数据文件的指针。主键索引和辅助索引是独立的。
- InnoDB的B+树主键索引的叶子节点就是数据文件，辅助索引的叶子节点是主键的值；MyISAM的B+树主键索引和辅助索引的叶子节点都是数据文件的地址指针。
B+树索引性能分析
- 一般使用磁盘I/O次数评价索引结构的优劣
- 预读：磁盘一般会顺序向后读取一定长度的数据(页的整数倍)放入内存
- 局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用
- B+Tree节点的大小设为等于一个页，每次新建节点直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，就实现了一个节点的载入只需一次I/O
- B+Tree的度d一般会超过100，因此h非常小(一般为3到5之间)
MyISAM索引实现(非聚集)
MyISAM索引文件和数据文件是分离的
主键索引
其它索引
InnoDB索引实现(聚集)
- 数据文件本身就是索引文件
- 表数据文件本身就是按B+Tree组织的一个索引结构文件
- 聚集索引-叶节点包含了完整的数据记录
- InnoDB表必须有主键，并且推荐使用整型的自增主键
InnoDB为什么推荐使用自增ID作为主键？
答：自增ID可以保证每次插入时B+索引是从右边扩展的，可以避免B+树和频繁合并和分裂（对比使用UUID）。如果使用字符串主键和随机主键，会使得数据随机插入，效率比较差。 - 非主键索引结构叶子节点存储的是主键值(一致性和节省存储空间)
主键索引
其它索引
索引最左前缀原理
在mysql建立联合索引时会遵循最左前缀匹配的原则，即最左优先，在检索数据时从联合索引的最左边开始匹配
