大家好，我是“Stephen·谢”，应一些需要，今天跟大家简单说说数据库的树形结构加索引的查询优化思路。
数据库在执行SQL语句的时候默认的方式是根据搜索条件进行全表逐一扫描，遇到条件匹配的就加入扫描结果集合。如果我们对某一字段增加索引，查询时就会先去索引列表中一次定位到特定值的行数，大大减少遍历匹配的次数，所以能明显增加查询的速度。
我们知道，数据库查询是数据库最主要的功能之一，我们都希望查询数据的速度尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找，当然这种时间复杂度为O(n)的算法在数据量很大的时候显然是糟糕的，于是有了二分查找、二叉树查找等。但是二分查找要求被检索的数据有序（就是按照某个字段已经排好顺序了），而二叉树查找只能应用于二叉查找树，但是数据本身的组织结构不可能完全满足各种数据结构。所以，在原本的数据之外，数据库系统维护者还创造出了满足特定查找算法的数据结构，这些数据结构以某种方式引用原本数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
通俗地说，索引的原理就是通过不断的缩小想要获得数据的范围来筛选出最终想要的结果，同时把随机的事件变成顺序的事件，也就是我们总是通过同一种查找方式来锁定数据。
目前大部分数据库系统及文件系统都采用B-Tree和B+Tree作为索引结构。（至于什么是B+树和B-树以及他们各自的特性和用法将在后面的文章中详细讲解）
下面我们以B+树索引查找来举例：
如上图，浅蓝色的块我们称之为一个磁盘块，可以看到每个磁盘块包含几个数据项（深蓝色所示）和指针（黄色所示），如磁盘块1包含数据项17和35，包含指针P1、P2、P3，P1指向小于17的磁盘块，P2指向在17和35之间的磁盘块，P3指向大于35的磁盘块。真实的数据存在于叶子节点即3、5、9、10、13、15、28、29、36、60、75、79、90、99。非叶子节点不存储真实的数据，只存储指引搜索方向的数据项，如17、35并不真实存在于数据表中。
B+树的查找过程 ：
如图所示，如果要查找真实数据29（真实数据29存在于最下方叶子节点中，系统是从最上方的根开始查），那么系统首先会把磁盘块1由磁盘加载到内存，此时发生一次IO（在数据库中指读写操作），在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存IO时间因为非常短（相比磁盘的IO）可以忽略不计，通过磁盘块1的P2指针指向地址把磁盘块3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘块3的P2指针，再通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询，总计三次IO。真实的情况是，3层的B+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要上百万次的IO，显然成本非常非常高。
PS附.（B+树的特性）
通过上面的分析，我们知道IO次数取决于B+数的高度h，假设当前数据表的数据量为N，每个磁盘块的数据项的数量是m，则有h=㏒(m+1)N，当数据量N一定的情况下，m越大，h越小；而m = 磁盘块的大小 / 数据项的大小，磁盘块的大小也就是一个数据页的大小，是固定的，如果数据项占的空间越小，数据项的数量越多，树的高度越低。这就是为什么每个数据项，即索引字段要尽量的小，比如int占4字节，要比bigint8字节少一半。这也是为什么B+树要求把真实的数据放到叶子节点而不是内层节点，一旦放到内层节点，磁盘块的数据项会大幅度下降，导致树增高。当数据项等于1时将会退化成线性表（此时并不是树形结构了，也便无索引）。
