以前有一群人，发明了数据库，能够把数据结构化地存储起来，他们很高兴。每次需要查数据的时候就一行一行地找。随着数据越来越多，问题出现了：一行一行找数据真tmd费劲。于是人们考虑到了图书与目录的关系，应用到数据库上，索引就出现了。
问题：查询数据库速度慢
方案：添加索引，就像为图书添加目录
我们的主角就这么登场了----索引
期初，人们直观地想到了利用HashMap<Integer, LinkedList<Record>>的形式去存储数据，根据一个主键ID值映射一个hash值，如果两个ID值映射到了同一个hash值上也没有关系，那就为一个hash值配对一个链表，在查找的时候先用ID映射到hash值，再在链表中遍历所有ID找到匹配的。这个办法查询效率很高，基本O(1)，但有人也看出来了缺点，就是不支持区间查询。当我们需要查询ID在10和20之间的记录时，只能这么查询20次。因此key-value形式的索引只适合于单点查询的场景，比如许多NoSQL。
问题：key-value形式的索引查询很快，但是很难进行区间查询
方案：改用线性数组形式的索引，区间查询 so easy
改用线性数组作为索引结构，ID有序递增。这样的话，如果进行单点查询就使用二分法，时间复杂度O(logN)，区间查询更是非常的爽，只需两次单点查询即可。但是对于插入删除比较频繁的场景，这种结构就非常让人难受了。删除一个记录，就要把后面的记录都往前移动。添加也是麻烦。因此这种结构的索引只适合静态数据，比如，北京市2018年结婚情况统计表。
问题：线性表索引虽然查询性能很优秀，但是插入删除数据的时候需要大范围移动数据
方案：将线性数组结构改为线性链表来克服插入删除时候的麻烦，并且再建立一个二叉平衡树来维持O(logN)的查询效率。
图1 二叉树版索引，顺序查找和快速单点查找兼具
既然顺序表形式的索引依然有问题，改成二叉树形式的索引也是直接的想法。可以看出，二叉树形式的索引同时兼备了单点查找事件复杂度O(logN)和支持顺序查找的有点。但现在还是有问题。当我们想访问ID为4的数据时，就需要查找三层数据，并且这三层数据不一定在一个内存页上，也就是说有很大可能这个查询需要访问三个磁盘上的数据块，在机械硬盘时代，每次访问硬盘需要10ms，这样一个简单的7个数中查询1个数据竟然需要30ms，简直太慢了，何况如果有100万个数据的时候需要20层。这时候就需要解决树的高度问题，很显然将二叉树改为多叉树就能降低树的高度从而减少访问数据块的次数。
问题：二叉树虽然兼备了单点查询O(logN)和支持顺序查询的优点，但是因为树的高度问题，需要多次访问磁盘数据块造成查询缓慢。
方案：改为多叉树，以降低树高，减少磁盘访问
多叉树究竟有多少叉取决于磁盘数据块大小和每个索引结点的大小。innodb采用大约1200个叉。因此如果有三层索引的话理论上可以容纳1200的三次方大约17亿个结点，与二叉树相比，树的高度降低了不止一点点。
图2 多叉树结构的索引（B+树）
网友评论