在之前的关于innodb行格式的笔记里面，我们已经知道了，每行的头上有个next_record标志位记录的是下一个行的位置，所以行跟行之间是类似单链表的形式串起来的。
当一行记录被删除的时候，只需要改动next_record的指向，并不需要实际物理擦除，毕竟物理擦除很费时。被释放的空间，其实是被添加到了空闲空间链表中。
在innodb行格式这篇笔记以及之前的innodb逻辑存储结构这篇笔记里面了解了innodb数据页的格式，如下图所示：
从数据页的格式里面看到有个Page Directory，即页目录。在innodb逻辑存储结构这篇笔记里面提过一句，它是个稀疏目录。使用Page Directory可以用二分查找的方法快速定位到大致的位置，然后按链表查到想要的结果。
在每个数据页里面，行与行之间是单链表，同时数据页还有目录可以快速定位大致位置。而数据页和数据页之间，因为在File Header里面有FIL_PAGE_PREV和FIL_PAGE_NEXT分别指向上一个和下一个页面，所以数据页和数据页之间是双向链表。
那么我们可以大致画一下，我们要存的一行行记录在innodb里面存储是什么样子的：
大家都知道innodb的索引的数据结构是B+树。讲B+树之前，先来说一下我们最熟悉的二叉树。
我们知道二叉树这个数据结构，在完全平衡的情况下（即左右子树高度差不超过1），叫平衡二叉树，查询的时间复杂度是O(logN)。如果不够平衡，甚至退化成链表的时候，它的查询时间复杂度就变成了O(N)。
平衡二叉树，它的查询的时间复杂度是O(logN)，但是在mysql里面不能用它，因为树太高了，而mysql的数据都是存在磁盘上的，如果树太高，意味着读磁盘的次数变多，而磁盘的速度是很慢的，从而导致响应时间很长。
那么我们可以考虑多叉树，父节点有很多个子节点，这样一来树就可以变矮了。当然多叉树如果比较平衡的话，会更利于查找。
现在我们来看下B树的概念，在wikipedia关于B树的介绍上面：
在计算机科学中，B树（英语：B-tree）是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树（binary search tree）一个节点可以拥有2个以上的子节点。与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上
按照上面的定义，那么我们刚刚提到的平衡的多叉树，可以称为B树。
而B+树和B树的不同之处在于：
- B+树的非叶子节点不保存行记录只存储关键信息，所以B+树每个非叶子节点存储的关键字数更多，B+树的层级更少所以查询数据更快
- B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高
- B+树遍历所有数据只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描
- 如果经常访问的数据离根节点很近，那么这种情况下B树数据检索的时候会要比B+树快，因为B树的非叶子节点存储了整个行记录。但是反过来也可以说B+树的查询效率比B树更平衡
在学习innodb逻辑存储结构这篇笔记里面提到过，页的File Header里面有一个字段FIL_PAGE_TYPE是用来表示页的类型的，可以是数据页、索引页等。
也就是说页也可以用来存储索引，那么这种页就要索引页。但与学习innodb行格式这篇笔记里面提到的稍微有点不同，之前那篇笔记里面提到数据页里面存的是一行行的记录。索引页里面存的不是记录而是索引。
上面提到了二叉搜索树的查询时间复杂度是O(logN)，但在我们所知的数据结构中，哈希表的查询时间复杂度是O(1)，为什么innodb没有使用哈希表这种数据结构呢？
原因一：
因为哈希表会产生hash冲突，一般解决hash冲突的办法是开放寻址法和链表法。开放寻址法也就是如果当前位置冲突，则往后一个位置，如果还冲突，则再往后查找，知道找到一个空位，就放进去。链表法是将hash冲突的数据用一个链表存起来，当链表很长的时候，查询时间复杂度也差不多是O(N)。如果要减少冲突性，那么就要增大整体的存储空间，让哈希值尽量分散。
原因二：
哈希表适合等值查询，不适合范围查询。所以我们业务中的where id < 100这种查询是不适合用哈希表的。
数据结构中还有有序数组，它使用二分查找法的查询时间复杂度是O(logN)，为什么不用这种数据结构呢？
是因为为了维护有序性，当插入数据或删除数据的时候，就要挪动后面的元素，导致开销较大。
所以还是B+树更加合适。