深入浅出数据库索引原理数据库索引 _小知识

数据库索引(简单的数据库索引原理) 。
索引的使用非常简单。只要能写语句创建表，就一定能写语句创建索引。你必须知道，这个世界上没有不能创建表的服务器端程序员。但是，会用索引是一回事，深刻理解索引的原理，能正确使用索引又是另一回事。这是一种完全不同的状态(我自己还没有达到这种状态) 。大多数程序员对索引的了解仅限于“索引可以使查询更快”的概念。
为什么要给表添加主键？
为什么索引会使查询更快？
为什么索引会降低写入、修改和删除的速度？
在什么情况下应该同时在两个字段上建立索引？
他们可能无法回答这些问题。知道这些问题的答案有什么好处？如果开发的应用程序使用的数据库表中只有10，000条数据，那么知道和不知道真的没有区别。但是，如果开发的应用程序有几亿甚至几十亿的数据，如果没有深刻理解索引的原理，编写的程序根本不会运行，就像如果卡车装有汽车发动机，卡车还能拉货吗？
接下来，我想解释一下上面的一些问题，希望对读者有所帮助。
网上很多解释索引的文章是这样描述索引的:“索引就像书籍的目录，通过它可以准确定位书籍的具体内容。”这句话很对，但就像脱裤子放屁，说了又不说，通过目录找到书的内容自然比一页一页翻过来要快，用索引的人很难知道通过索引定位数据比直接一个一个查询要快。
要理解索引原理，必须明确一个数据结构“平衡树”(非二进制)，即b树或b+树。重要的事情说三遍:“平衡树，平衡树，平衡树” 。当然，一些数据库也使用散列桶作为索引数据结构。然而，主流的关系数据库管理系统都将平衡树作为数据表的默认索引数据结构。
我们通常在创建表时向表中添加主键。在某些关系数据库中，如果在创建表时没有指定主键，数据库将拒绝执行创建表的语句。事实上，具有主键的表不能称为“表” 。一个没有主键的表，它的数据无序地放在磁盘存储器上，一排排排列整齐，非常接近我认知中的“表” 。如果把主键给了表，那么表在磁盘上的存储结构就会从整齐的排列结构变成树形结构，也就是上面提到的“平衡树”结构，换句话说，整个表就会变成一个索引。是的，同样，整个表成为一个索引，这被称为“聚集索引” 。这就是为什么一个表只能有一个主键，一个表只能有一个“聚集索引”，因为主键是用来把“表”的数据格式转换成“索引(平衡树)”的格式的。

文章插图

上图是主键表(聚集索引)的结构图。画面不是很好，我们就看一下吧。树的所有节点(除了底部)的数据都是由主键字段中的数据组成的，也就是我们通常指定的主键的id字段。底部是真实表格中的数据。假设我们执行一条SQL语句:
从表中选择*其中id = 1256
首先根据索引定位值1256所在的叶节点，然后通过叶节点获取id等于1256的数据行。这里我就不解释平衡树的操作细节了，但是从上图可以看出，树中有三层，从根节点到叶节点只需要三次搜索就可以得到结果。下图

文章插图

如果一个表中有1亿条数据，需要找到其中一条，按照常规逻辑，如果要一一匹配，最坏的情况是需要匹配1亿次才能得到结果。使用大O符号是O(n)最差的时间复杂度，这是不可接受的。而且，很明显，这1亿条数据不能一次读入内存供程序使用。所以这1亿匹配就是1亿没有缓存优化的IO支出。如果将表转换成平衡树结构(一棵非常茂盛的树，节点很多)，假设树有10层，只需要10个IO开销就能找到需要的数据，速度呈指数级增长。大O记法为O(log n)，N为总记录树，基数为树的分叉数，得出树的层数。换句话说，搜索次数是基于树的分叉数，记录总数的对数，用公式表示。

文章插图

程序是数学。log(1000000000，10)，其中10000000为记录数，10为树的分枝数(真实环境中的分枝数远远超过10) 。结果就是搜索次数，这里的结果从1亿减少到个位数。因此，索引的使用将极大地提高数据库查询的性能。
然而，任何事情都有两面性。索引可以提高查询数据的速度，降低写入数据的速度。原因很简单，因为平衡树的结构必须始终保持在正确的状态。添加、删除和修改数据会改变平衡树各节点中索引数据的内容，破坏树结构。因此，每次数据发生变化时，DBMS都必须重新组织树(索引)的结构，以确保其正确性，这将带来大量的性能开销。