索引原理简单理解

关于聚集索引

没有加主键的数据表，数据是一行一行无序整齐的存放在存储器之中，如果增加主键，也就是所谓的聚集索引，则会变成棵平衡树，【整个】数据表的结构从【无序表格】变成一棵【平衡树(B tree(-p1)】，所以一个表只能有一个聚集索引
注:-p1：左节点小于右节点,等于当前节点则命中，小于走左子节点，大于走右子节点知道找到符合的节点值，如果没有则认为无节点)

关于非聚集索引

非聚集索引不改变整个表的结构，而是将指定的索引字段的值构建为一棵单独的平衡树，每给一个字段建立一个索引，就会把【字段中的值】复制出来建立一棵树，会增加表的体积占用磁盘空间，查询时，会在现在这棵单独的平衡树中查询，到符合数据的主键，再使用主键的值去聚集索引中查询数据行

关于大O计算公式

假如一张表有N条数据 ，最坏的情况要匹配N次才能得到结果，用大O标记法就是O(n)最坏时间复杂度， 这N次匹配在不经缓存优化的情况下就是N次IO开销 。

如果把这张表转换成平衡树结构，假设这棵树有10层，那么只需要10次IO开销就能查找到所需要的数据， 速度以指数级别提升，用大O标记法就是O(log n)，n是记录总树，底数是树的分叉数，结果就是树的层次数。用公式来表示就是 image.png