数据索引采用的数据结构是B+树，B+树是B树的改进版本。为了在实现的时候思路更加清晰，所以先写下一篇blog记录我对索引以及B+树的认知和认知的变化情况。
索引
索引是帮助数据库高效获取数据的排好序的数据结构，这里只需要了解到索引能实现查找数据即可，具体的编码方式会在文件系统介绍里仔细说明。
组成
一个完整的索引数据包含两部分：排序的值和对应的数据。在通常情况下，索引会按照索引字段进行排序并存储，存储引擎会根据编码类型和排序规则进行排序。
索引的数据具体保持的什么需要视情况而定，存储引擎的不同以及索引类型的不同都会导致索引数据存储的方式和结果不同
分类
聚族索引
索引的数据区就是存储这一行对应表中完整的数据。如果是非主键索引，那么数据区就是存储的主键索引地址。
这种策略会造成空间的浪费，并且会提高维护数据库的成本。但一个表数据查询的次数是要远远高于修改次数的，综合考虑，是利大于弊。
非聚族索引
主键索引的值不可重复。索引存储的数据其实是磁盘文件地址（数据结构同样是B+树，这种索引也称为非聚族索引）。但寻找到相应的索引后，就会根据磁盘文件地址寻找相应的真实数据并加载到内存中。
经过考量，mkDB采取聚族索引，因为这是一个玩具数据库，写这个项目主要是为了理解数据库的运行，归根到底还是练手而不是造轮子。这样加速了查找，也减少了编码消耗的时间。
在代码实现中，如果调用接口的时候不定义主键，默认将第一个元数据作为主键。为了更好的排序，会将第一个数据通过哈希函数转换成整型，有利于后续排序。因为索引是根据索引字段来排序插入的，作为一颗B+树来维护，整型是最容易操作的。
作用
索引作为一种有序并且查询效率极高的数据结构，可以快速的查找目标数据。
为什么是B+树
要解决这个疑问，要先明白数据引擎需要什么样的结构，在此之前，还要先了解数据引擎需要的是什么，然后根据需求对应的设计或者寻找适合的数据结构。
我们知道，对于一个程序而言，对数据库只有一点要求，就是在不出错的情况下尽可能快。因此，快是数据引擎需要的。
了解了数据引擎的需要后，就该分析数据引擎的需要了。速度是根本，提升速度的办法有减少磁盘读写次数，减少数据库上锁时间等，毕竟一个人的快不是快，一群人快才是真的快。
减少磁盘读写次数：
数据库建立在外存上，要想速度快就得减少读取次数，最好能一次性把数据全部读入。这样红黑树、哈希表、AVL树，链表还有链表改进的跳表这些都不是一个好的选择，因为这些结构的数据分散，不能快速大量读取。
减少数据库上锁时间：
要减少数据库上锁时间，那数据在创建和删除过程应该尽可能地少操作，不能像数组一样，插入和删除都需要O(n)的时间复杂度，得像链表这样插入和删除都只需要O(1)的时间复杂度。
综上，可以确定数组，链表，红黑树，哈希表都不适合作为数据引擎存储的数据结构，因为他们的优缺点都很明显。聪明的人可能已经想到，为什么要做选择，难道不能用树存储数组吗？可以用树的结构存储数组，这样不是既减少了磁盘读写次数，也减少了数据操作时的步骤也就是减少数据库上锁的时间。B+树就是在这样条件下诞生的。
至此，确定采用B+树。
如何使用B+树
确定了B+树后，就到了设计树节点的时候了。树的节点究竟该存储哪些内容呢？
根节点
B+树的根节点作为一个基本单位页，与子节点独立一个文件，后缀为.idx。文件里面定义了根节点存储的键以及对应子节点的偏移位置，这些键都已经按从小到大的顺序排好序，搜索时只需要遍历找到键对应的范围然后进入对应的子节点即可。
在具体实现上根节点会常驻内存。
子节点
根节点下面有很多个子节点，子节点的数量等于根节点存储的键的数量，并且子节点最大值或最小值就是对应根节点所存储的键。
子节点每个键值后面就是数据页的页号。找到键值后根据页号计算偏移量读取叶子节点的数据。
举个例子，一个三阶B+树，根节点就有3个键，假设分别为1，5，9。相应地，子节点也有3个，第一个子节点的键取值范围是[1,5)，最小值等于根节点的1，以此类推，第二个子节点的键取值范围在[5,9)，最小值是根节点的5，第三个子节点取值则是[9,13)，如果出现了大于13的键那么B+树根节点会扩充。
在具体实现时子节点位于外存。
叶子节点
子节点会指向叶子节点，叶子节点就是对应的数据了。只要找到子节点对应的键，我们就能够找到该键所对应的数据的地址。叶子节点与叶子节点之间会通过双向链表连接。
叶子节点即数据页，存放在.db文件中。叶子节点存放着各种记录信息。
如何实现B+树
了解B+树原理后就可以动手实现B+树了，具体代码移步github主页。
扩展
LSM树
除了B+树还有LSM树同样可以实现高效的索引，LSM树与B+树不同的地方在于B+树修改数据时是直接原地擦除并修改，而LSM树是直接追加一条修改记录，并在一段时间后合并记录。原地擦除的策略更契合传统机械硬盘的，而追加修改这种策略与如今更为流行的固态硬盘更为契合。结合难度综合考虑，这里选择的是B+树。
