索引
index
一般读多写少，索引是为了加快查询速度
不断地缩小想要获取数据的范围来筛选出最终想要的结果，同时把随机的事件变成顺序的事件
访问磁盘的成本大概是访问内存的十万倍左右
寻道时间、旋转延迟、传输时间(可以忽略不计)
局部预读性原理
二叉树 -> 平衡二叉树 -> B tree -> B+ tree
- linear: O(N)
- binary search tree: O(logN)
- hash: only suitable for single value search
- 二叉树、红黑树: 逻辑上很近的节点（父子）物理上可能很远
MySQL B+ tree: 增加了顺序访问指针，高了区间访问性能，极大提到了区间查询效率(无需返回上层父节点重复遍历查找减少IO操作)。
索引很大，需要存储到磁盘 一个B+Tree节点大小设为一个页大小
primary key, unique, index
索引类型(不同存储引擎支持不同): hash - 单条快 b tree - innodb default
-
聚集索引（clustered index） - InnoDB 索引和数据放于同一个文件 包含记录的全部数据，双向链表 有利于范围查询 ckey-data 每张表一个
-
辅助索引（secondary index）（非聚集索引） - MyISAM skey-bookmark(ckey, 相应行数据的聚集索引键)
method
根据检索条件创建索引 索引也不宜过多，占存储空间，影响性能 优化sql，缩小检索范围
MyISAM
采用非聚簇索引-MyISAM myi索引文件和myd数据文件分离，索引文件仅保存数据记录的指针地址 rm -表定义、 myi -myisam索引、 myd-myisam数据
InnoDB
- support transaction
- high extensibility
- redo/undo
- 行级别锁 ＊page cache LRU 要求表必须有pk，未指定mysql会自动选择一个可以唯一表示数据记录的列作为主键，如果不存在这样的列，mysql自动为InnoDB表生成一个隐含字段(6个字节长整型)作为主键
之上有二级索引（非聚簇索引），需要二次查找，加快速度 比如像复合索引、前缀索引、唯一索引，辅助索引叶子节点存储的不再是行的物理位置，而是主键值
查询条件中为非主键时就需要二级索引
maintain index cost
- insert new line
- page split 使用UUID（random id）可能导致index效率低于 full table scan。建议使用auto_increment。
最大填充因子：页大小的 15/16，留出部分空间用于以后修改
选择
单次来看聚簇索引效率低，但是由于数据的相关性和提前加载。所以总的来说性能更高。
聚簇索引适合用在排序的场合，非聚簇索引不适合
| cluster index | non clustern index | |
|---|---|---|
| ordering | yes | not suitable |
| range | yes | no |