恒奥中心，快凌晨了，希望这是今年最后一次通宵的测试。也许以后会离开这里，但现在有留下的理由。北京突然就开始热了，忽而今夏。
要优化索引！要优化索引！这可能是发现某个查询比较慢时项目经理最常说的一句话。确实，索引就是为了提高数据库查询效率的，就像一本书的目录一样。
实现索引的方式有很多种，所以就引入索引模型的概念。可以用于提高读写效率的数据结构很多，这里说三种常见简单的：哈希表、有序数组、搜索树。
哈希表是一种以 key-value 存储数据的结构，我们只要输入待查找的 key 就可以找到对应的 value。哈希的思路很简单，把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。
如果多个 key 经过哈希后出现同一个值，处理冲突的一种方式是拉出一个链表。取 value 的时候顺序遍历拉链表就好了。
优点是新增很快，但缺点就是区间查询速度很慢。所以哈希表这种结构适用于只有等值查询的场景，比如 Memcached 及其他一些 NoSQL 引擎。
而有序数组在等值查询和范围查询场景中的性能就都非常优秀。但在需要更新数据的时候就麻烦了，你往中间插入一个记录就必须挪动后面所有的记录，成本太高。
所以有序数组索引只适用于静态存储引擎，比如保存的是2018年所有质押业务信息，这类数据是历史的，不会更改的。
二叉搜索树更是课本里的经典数据结构了，特点是每个节点的左孩子小于父节点，父节点又小于右孩子。查询的时间复杂度为 O(log(N))，当然为了维持这个查询复杂度需要保证这个树是平衡二叉树，为了做这个保证，更新的复杂度也是 O(log(N))。
树可以是多叉，孩子之间的大小保持从左到右递增。二叉树是搜索效率最高的，但实际上大多数的数据库存储并不使用二叉树，原因是索引不止存在内存中，还要写到磁盘上。为了让一个查询尽量少读磁盘，就必须让查询的过程访问尽量少的数据块，就应该使用 N 叉树，N取决于数据块的大小。
在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表，InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的。
每一个索引在InnoDB里面对应一棵 B+ 树。
(下个月找时间再填坑。。因为我实在太困了😹。。)
##
