高级应用篇四

问题：在工作中，为了加速数据库中数据的查找速度，我们常用的处理思路是，对表中数据创建索引。那你是否思考过，数据库索引是如何实现的呢？底层使用的是什么数据结构和算法呢？

解题思路

1，定义清晰问题：功能性问题，限定需要解决问题的范围。假设我们要解决的问题，只包含如下两个常用的需求：

根据某个值查找数据：select * from user_table where id = 1234

根据区间值来查找某个数据：select * from user_table where id > 1234 and id < 2345

除了功能性需求之外，往往还需要涉及一些非功能性需求，比如安全，性能，用户体验等等。对于非功能性需求，我们着重考虑性能方面的需求。也就是执行效率和存储空间。

2，尝试用学过的数据结构解决这个问题

需要支持快速查询，插入等操作的动态数据结构，我们已经学习过散列表，平衡二叉树，跳表。

散列表：查询性能很好，时间复杂度是O(1)。但是散列表不能支持按照区间快速查找数据。所以散列表不能满足我们的需求。

平衡二叉树：平衡二叉树查询性能很高，时间复杂度是O(logn)。并且对树进行中序遍历，可以得到一个从小到大右序的数据序列，但仍然不足以支持按照区间快速查找数据。

跳表：跳表是在链表之上加上多层索引构成的。它支持快速地插入，删除数据，对应的时间复杂度是O(logn)。并且跳表也支持按照区间快速地查找数据。这样看来，跳表是可以解决这个问题。实际上，数据索引所用到的数据结构跟跳表非常相似，叫做B+树。

3，改造二叉查找树来解决这个问题

为了让二叉树支持按照区间来查找数据，我们可以对它进行这样的改造：树中的节点并不存储数据本身，而是只是作为索引。除此以外，我们把每个叶子节点串在一条链表上，链表中的数据是从小到大有序的。改造之后，如果我们要求某个区间的数据。我们只需要拿区间的起始值，在树中进行查找，当找到某个叶子节点之后，我们再顺着链表往后遍历，直到链表中的结点数据值大于区间的终止值为止。

但是，我们要为几千万，上亿的数据构造索引，如果将索引存储在内存中，尽管内存访问速度非常快，查询效率非常高，但是，占用的内存会非常多。

我们可以借助时间换空间的思路，把索引存储在硬盘中，而非内存中。硬盘的访问速度是毫秒级的，而内存的访问速度是纳秒级别的，取同样的数据，从磁盘中读取花费的时间是从内存中读取花费时间的上万倍。这样数据的查询效率就相应降低很多。

二叉查找树，经过改造之后，支持区间查找的功能就实现了。不过为了节省内存，如果把树存储在硬盘中，那么每个节点的读取，都对应一次磁盘IO操作。树的高度就等于每次查询数据时磁盘IO操作的次数。

比起内存读取操作，磁盘IO操作操作非常耗时，我们优化的重点就是尽量减少磁盘IO操作，也就是尽量降低树的高度。那如何降低树的高度？

对于相同的数据构建m叉树索引，m叉树中m越大，那树的高度就越小，那m叉树中的m是不是越大越好呢？不管内存中的数据，还是磁盘中的数据，操作系统都是按页（一页大小通常是4KB)来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次IO操作。所以我们在选择m大小的时候，要尽量让每个节点的大小等于一个页的大小。读取一个节点，只需要一次磁盘IO操作。

B+树总结

数据库索引实现，依赖的底层数据结构是B+树。它通过存储在磁盘的多叉树结构，做到了时间，空间的平衡，既保证了执行效率，又节省了内存。

特点:

1，每个节点中子节点的个数不能超过m, 也不能小于m/2；

2，根节点的子节点个数可以不超过m/2, 这是个例外

3，m叉树之存储索引，并不真正存储数据，这个有点类似跳表

4，通过链表将叶子节点串联在一起，这样可以方便按区间查找

5，一般情况下，根节点存储在内存中，其它节点存储在磁盘中。

B树和B+树的不同

B+树中节点不存储数据，只是索引，而B树中的节点存储数据

B树中的叶子节点并不需要链表来串联

B树只是一个每个节点的子节点个数不能小于m/2的m叉树。