数据索引

数据库的索引，对于提升查询效率非常重要。
就如同翻一本书，我们想找到书中某一页，如果一页一页的去翻，那实在太慢了，而且数据库的持久化，都是将数据存储在硬盘中的。硬盘I/O操作本身就非常慢，如果再用笨拙的方式，那无疑查询会非常恼火。

索引可用通俗的解释为一本书的目录。但这只是一个简单的说法而已。

索引的本质其实是一种能够帮助我们快速进行查询的数据结构。

既然如此，就有各种各样的数据结构可以帮我们进行查找优化，例如
二叉树，哈希表，红黑树等等。

索引和数据

索引本质是一个数据结构，那么索引是如何帮助我们快速进行查找的呢？

首先索引本身也是存储在硬盘中的，索引的节点，包含了能让我们直接定位到数据的元素，通常是数据在磁盘存储的地址。那么我们就能先通过索引的快速查找，以很低的时间复杂度，直接拿到数据存储在磁盘的地址，然后直接将数据从磁盘读取出来就行了。

以BST为例，我们对BST的查找复杂度是O(logN)的，相比直接进行磁盘寻址，能大大减少I/O次数，性能也就得到了提升。

但是BST有很大的缺陷，它没有平衡性，很可能数据在不断地插入过程中，让BST退化成了链表。

这样的话，它的查询效率就和全表扫描没有啥区别了。

所以我们可以用平衡的树来优化它。平衡的树有AVL和红黑树
它们的区别是，AVL是严格的平衡二叉树，其所有节点的左右子树高度不会相差超过1，而红黑树是弱平衡的，它能确保没有路径会比另外的路径长两倍。

ALV的缺点在于，它的旋转操作非常耗时，甚至超过了它本身数据结构带来的收益。它只适合插入少，查询读取多的场景，所以并不适合用来作数据库索引

而红黑树由于它的弱平衡，所以它的插入性能比ALV好，但是问题同样存在

红黑树的高度增长太快了，这样也会大大的增加查找的次数。

而MySQL数据库使用的是什么数据结构作为索引呢？

不是上面的任何一种，而是一种B+Tree
类似下面的这种数据结构

它有以下几个特点：
1.每一个节点存储多个元素
2.每个节点中的元素是有序排列的
3.每个节点中的两个相邻元素之间，存储的是子节点的指针。
4.子节点中的元素，一定大于等于父节点指针左边的元素，小于等于父节点指针右边的元素。
5.非叶子节点不存储data，只存储索引key；只有叶子节点才存储data

通过以上的特点，由于它每一个节点能存储多个元素的，它能实现对很大的数据量进行存储，同时树的高度依旧保持很低。

并且在每个节点的元素是有序排列的，在针对节点中的元素进行查找时候，能使用二分查找，快速的扫描。

而MySQL的存储引擎的B-Tree还有一些特殊的地方：
在每个叶子节点之间，新增了指向相邻节点的指针，这样就能提升区间访问的性能，例如我要查找id大于19的记录，那么只需要走B+Tree定位到19，然后顺着叶子节点的指针访问就行了。

再简单说说InnoDB和MyISAM 它们的底层虽然都是B+Tree，但是还是有区别的，在于InnoDB的叶子节点就包含了一条记录的完整元素，而MyISAM的叶子节点还是存储着磁盘地址。

索引就意味着查询性能提升？

很遗憾，索引只能在某些情况提升查询效率。我们在编写SQL语句的时候一定得注意，尽量让查询走索引。
例如PostgreSQL,对于LIKE查询前后模糊的情况，它是并不支持索引的，但是可以通过插件pg_trgm 来让模糊查询也能走索引。
PostgreSQL可以算是我现在最喜欢的一个关系型数据库了，它东西很多，功能也很强大。