索引

索引是一种高效查找的数据结构，减少与磁盘的IO。

全表扫描的时候，由于数据分布在不同的位置上面，读取数据的时候，磁臂需要前后摆动查找数据，这样操作非常消耗时间，时间复杂度为O(n)。

当以(key,value)形式在二叉搜索树节点存储数据，key存储值，value存储行的文件指针。以二叉搜索树数据结构建立索引的时候，时间复杂度为O(log₂n)。

以下图为例，当搜索值为40,

第一次搜索的时候，40与30比较，40大于30，从30的右子树搜索，搜索范围变成（38、34、40）7/2=3个节点
第二次搜索的时候，40与38比较，40大于38，从38的右子树搜索，搜索范围变成（40）7/4=1个节点
第三次搜索的时候，40与40比较，40等于40，找到要搜索的数据，搜索范围变成7/8=0

二叉搜索树

由次类推，n个元素，k次搜索的时候，搜索范围变成n/2的k次方，当搜索范围等于1节点个的时候，2的k次方=n，k=log₂n

缺点：

1、创建和维护索引需要耗费时间，随着数据量的增加，所消耗的时间也会增加；
2、索引也需要占用磁盘空间;
3、降低了更新表的速度，当对表中的数据进行增加，删除和修改的时候，索引也会动态的维护。