数据库索引的作用（数据库索引的实现原理到底是什么样的呢？）

作为一个程序员，在日常的工作中，肯定是离不了数据库的。使用数据库，那一般就会用到索引，但是，很多时候，我们虽然使用索引，但是却并不知道其中的原理。今天，我们就来聊聊数据库索引的实现原理。

数据库为什么需要用到索引？

比较经典的介绍索引作用的案例就是图书馆了。

如果没有索引，我们要去找图书馆的一本名叫《十万个为什么》的书，就需要在整个图书馆里面大海捞针似的寻找。

如果我们按照一些规则进行一个分类，例如：

图书馆一楼是文学类，二楼是科技类，三楼是历史类；然后每层楼又分了很多区，例如：中国古代史，中国近代史，外国古代史，外国近代史等等；最后再按照书名的首字母排序。

这样，我们就能够很好的定位我们要找的书的位置。

而这就是索引的用处：提高查询的效率。

数据库有哪些索引数据结构呢？

我们常见的索引数据结构有，哈希索引和B+树索引。

1. 哈希索引

哈希索引顾名思义，就是使用哈希算法，将键值转化为哈希值从而进行检索的方式，这种方式的优点在于，每次检索时，只需要通过哈希算法计算出结果，然后就可以一次定位到目标位置，检索的速度非常快。

2. B+树索引

要说树，我们就需要说一下经典的二叉树，大家相信在课本上都有学到过。

当然，二叉树是不适合用于数据库索引的，因为在数据量大时，树的高度就非常可怕了，检索速度也就快不起来。本来索引的用处就是为了在数据量大时能够快速定位，这样就有点背道而驰了。

既然二叉树满足不了，那多叉树呢？

于是，就有了B树。

B树不再是二叉结构，而是使用了多叉结构，因此B树又叫“平衡多路排序树”。它的所有节点都是存储空间，当执行插入和删除操作时，不需要在移动大段的内存数据了，当然，这样做以后，插入和删除时，就可能会引起B树的结构变化。

在B树的基础上，我们再进行改进，就有了现在的B+树。

B+树中，我们不再将数据存放在非叶子节点中了，所有数据仅保存在叶子节点，所有的叶子节点之间，增加了指针进行链接。

为什么数据库要使用B+树索引结构呢？

不使用二叉树的原因我们已经说过了，但是感觉B树也不错，为什么不用呢？

先说说B树的好处，由于B树在每个节点都存储数据，所以，如果我们查询的时候，目标值位置刚好在B数的非叶子节点上，检索的层数就会比B+树少很多，时间也就能快很多。而B+树，无论如何，检索都会到达叶子节点上。

同样，由于B树的非叶子节点存储了数据，因此，B树的高度也比B+树要矮，所以，即使都到达叶子节点查询，B树还是会快一些。

这样看来，B树不是比B+树有优势呢？下面，我们就来说说B+树的优势——扫库。

要知道，我们在做数据库查询的时候

select * from T where id = ？

写这样的查询语句并不是数据库主要的开销场景，很多时候，我们会写这样的SQL

select * from T where datetime > ?

这个时候，就需要进行区间查询，对于确定区间位置，B树和B+树都是一样的，而且基本都是在内存里完成的。但是，一旦要进入数据库查询的时候，B树的劣势就出现了，B树必须通过中序遍历，反复进行多次磁盘的IO，而B+树由于每个叶子节点间有指针链接，一次IO，就把这个区间拿出来了。

这也就是为什么我们在数据库中不使用B树，要使用B+树的原因。

那么哈希索引呢？

哈希索引其实一个理由，如果在进行等值查询的时候，哈希索引是有绝对优势的，比B树的优势还大非常多。

在等值查找时，哈希索引的时间复杂度为O(1)，但是B+树是O(log n)。

但是，我们使用数据库不可能只有等值查找，还有>、