索引的进化
在实际的应用中，这样的定位效率仍然不能满足需求。很多人可能已经想到了，通过排序和查找算法来减少IO的访问。因此我们开始尝试对Dense Index进行排序存储,并且期望利用排序查找算法来减少磁盘IO。
1.折半块查找
对Dense Index排序
需要一个数组按顺序存储索引块地址。以块为单位，不存储所有的行的地址。
这个索引块地址数组，也要存储到磁盘上。将其单独存放在一个块链中，如下图所示。
折半查找的时间复杂度是O(log 2(N))。在上面的列子中，dense索引总共有10,000个块。假设1个块能存储2000个指针，需要5个块来存储这个数组。通过折半块查找，我们最多只需要读取5(数组块)+ 14(索引块log 2(10000))+1(数据块)=20个块。
2.Sparse Index
实现基于块的折半查找时发现，读出每个块后只需要和第一行的键值匹配，就可以决定下一个块的位置(方向)。 因此有效数据是每个块(最后一个块除外)的第一行的数据。还是根据减少无效数据IO的原则，将每一个块的第一行的数据单独拿出来，和索引数组的地址放到一起。这样就可以直接在这个数组上进行折半查找了。如下图所示，这个数组就进化成了Sparse Index。
因为Sparse Index和Dense Index的存储结构是相同的，所以占用的空间也相同。大约需要10个块来存储10000个Dense Index块的地址和首行键值。通过Sparse索引，仅需要读取10(Sparse块)+1(Dense块)+1(数据块)=12个块.
3.多层Sparse Index
因为Sparse Index本身是有序的，所以可以为Sparse Index再建sparse Index。通过这个方法，一层一层的建立 Sparse Indexes,直到最上层的Sparse Index只占用一个块为止,如下图所示
- 这个最上层的Sparse Index称作整个索引树的根(root).
- 每次进行定位操作时，都从根开始查找。
- 每层索引只需要读出一个块。
- 最底层的Dense Index或数据称作叶子(leaf).
- 每次查找都必须要搜索到叶子节点，才能定位到数据。
- 索引的层数称作索引树的高度(height).
- 索引的IO性能和索引树的高度密切相关。索引树越高，磁盘IO越多。
- 在我们的例子中的Sparse Index，只有10个块，因此我们只需要再建立一个Sparse Index.通过两层Sparse Index和一层Dense Index查找时，只需读取1+1+1+1=4个块。
3.Dense Index和Sparse Index的区别
Dense Index包含所有数据的键值，但是Sparse Index仅包含部分键值。
Sparse Index占用更少的磁盘空间。
Dense Index指向的数据可以是无序的，但是Sparse Index的数据必须是有序的。
Sparse Index 可以用来做索引的索引，但是Dense Index不可以。
在数据是有序的时候，Sparse Index更有效。因此Dense Index仅用于无序的数据。
索引扫描(Index Scan)实际上是对Dense Index层进行遍历。
5.簇索引(Clustered Index)和辅助索引(Secondary Index)
如果数据本身是基于某个Key来排序的，那么可以直接在数据上建立sparse索引，而不需要建立一个dense索引层(可以认为数据就是dense索引层)。 如下图所示：
这个索引就是我们常说的“Clustered Index”,而用来排序数据的键叫做主键Primary Key.
一个表只能有一个Clustered Index,因为数据只能根据一个键排序.用其他的键来建立索引树时，必须要先建立一个dense索引层，在dense索引层上对此键的值 进行排序。这样的索引树称作Secondary Index.
一个表上可以有多个Secondary Index.
对簇索引进行遍历，实际上就是对数据进行遍历。因此簇索引的遍历效率比辅组索引低。如SELECT count(*) 操作，使用辅组索引遍历的效率更高。
6.范围搜索(Range Search)
由于键值是有序的，因此可以进行范围查找。只需要将数据块、Dense Index块分别以双向链表
的方式进行连接， 就可以实现高效的范围查找。如下图所示：
范围查找的过程：
选择一个合适的边界值，定位该值数据所在的块
然后选择合适的方向，在数据块(或Dense Index块)链中进行遍历。
直到数据不满足另一个边界值，结束范围查找。
这分明就是传说中的B+Tree.
6.索引上的操作
插入键值、删除键值、分裂一个节点、合并两个节点，这些操作就不介绍了。
