三种常见的数据结构： 哈希表、有序数组和搜索树。
- 哈希表这种结构适用于只有等值查询的场景，通过key 算出位置（可能会重复）每个位置上的valus是一个数组，按顺序遍历，用二分法就可以快速得到，这个时间复杂度是 O(log(N))。有序数组索引只适用于静态存储引擎
- 哈希冲突的处理办法：链表
- 二叉树，二叉搜索树的特点是：父节点左子树所有结点的值小于父节点的值，右子树所有结点的值大于父节点的值。这个时间复杂度是 O(log(N))。但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在内存中，还要写到磁盘上。
- N 叉树由于在读写上的性能优点，以及适配磁盘的访问模式，“N 叉”树中的“N”取决于数据块的大小。
- 数据库存储大多不适用二叉树，因为树高过高，会适用N叉树
InnoDB 的索引模型
- 在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。又因为前面我们提到的，InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的。
- 索引类型分为主键索引和非主键索引。
- 主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。
- 非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。
- B+树的叶子节点是page （页），一个页里面可以存多个行，内部有个有序数组，二分法
主键索引与非主键索引查询区别
- 非主键索引先查询非索引
- 基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。
索引维护
由于每个非主键索引的叶子节点上都是主键的值。主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。
一个数据页满了，按照B+Tree算法，新增加一个数据页，叫做页分裂，会导致性能下降。空间利用率降低大概50%。当相邻的两个数据页利用率很低的时候会做数据页合并，合并的过程是分裂过程的逆过程。
索引的创建问题
- 重新建索引是可以的
- 重新建主键相当于重新建表 （用空的alter操作，比如ALTER TABLE t1 ENGINE = InnoDB）
- 删除数据但是存储空间依然占用很大的问题，因为页分裂等原因，导致数据页有空洞，重建索引的过程会创建一个新的索引，把数据按顺序插入，这样页面的利用率最高，也就是索引更紧凑、更省空间。
覆盖索引
只有索引包含了where条件部分和select返回部分的所有字段才能达到真正的减少回表
- 查询的字段在索引的叶子节点中就是覆盖索引 select id from table where a=100
- 由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。
- 联合索引，在建立冗余索引来支持覆盖索引时就需要权衡考虑了
- 如果查询条件使用的是普通索引（或是联合索引的最左原则字段），查询结果是联合索引的字段或是主键，不用回表操作，直接返回结果，减少IO磁盘读写读取正行数据
最左前缀原则与索引下推
- 联合索引（a，b，c）起作用的索引是 单独查a 或 （a,b）或 （a,b,c ）然而 单独查b或c 以及（b，c）不起作用，B+ 树这种索引结构，可以利用索引的“最左前缀”，来定位记录。
- （a,b）中b起到作用就是索引下推，可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。在索引内部判断b是否满足条件，再选择回表
表的逻辑结构
表的逻辑结构 ，表 —> 段 —> 段中存在数据段(leaf node segment) ，索引段( Non-leaf node segment）
例子
- select * from T where k in(1,2,3,4,5) 树搜索5次 而 select * from T where k between 1 and 5 只需要1次
- mysql的myisam引擎支持事务，通过lock table，但是这样只能实现串行化隔离级别，崩溃也无法修复，
- “a > 5 and a < 10 and b='123'” 在ICP作用下的执行过程是什么样子的？
a) 把 a>5 and b='123'传入引擎
b) 引擎找到第一个a>5的行（这里是快速定位），如果发现b='123',找下一个，直到满足b='123',
c) 把找到的行返回给server层， server层根据a是否小于10决定要不要取下一个
