索引的产生
1. 键(Key)
首先，我们发现在多数情况下，定位操作并不需要匹配整行数据。而是很规律的只匹配某一个或几个列的值。 例如，图中第1列就可以用来确定一条记录。这些用来确定一条数据的列，统称为键(Key)
2.Dense Index
根据减少无效数据访问的原则，我们将键的值拿过来存放到独立的块中。并且为每一个键值添加一个指针， 指向原来的数据块。如图所示,
这就是‘索引’的祖先Dense Index. 当进行定位操作时，不再进行表扫描。而是进行索引扫描(Index Scan)，依次读出所有的索引块，进行键值的匹配。当找到匹配的键值后，根据该行的指针直接读取对应的数据块，进行操作。假设一个块中能存储100行数据，10,000,000行的数据需要100,000个块的存储空间。假设键值列(+指针)占用一行数据1/10的空间。那么大约需要10,000个块来存储Dense索引。因此我们用大约1/10的额外存储空间换来了大约全表扫描10倍的定位效率。
