转自 由浅入深理解索引的实现(2)

如果要看“由浅入深理解索引的实现(1)”，请点这里 。

教科书上的B+Tree是一个简化了的，方便于研究和教学的B+Tree。然而在数据库实现时，为了
更好的性能或者降低实现的难度，都会在细节上进行一定的变化。下面以InnoDB为例，来说说
这些变化。

04 - Sparse Index中的数据指针

? 在“由浅入深理解索引的实现(1)”中提到，Sparse Index中的每个键值都有一个指针指向
? 所在的数据页。这样每个B+Tree都有指针指向数据页。如图Fig.1所示：

Fig.1

? 如果数据页进行了拆分或合并操作，那么所有的B+Tree都需要修改相应的页指针。特别是
? Secondary B+Tree（辅助索引对应的B+Tree), 要对很多个不连续的页进行修改。同时也需要对
? 这些页加锁，这会降低并发性。

? 为了降低难度和增加更新(分裂和合并B+Tree节点)的性能，InnoDB 将 Secondary B+Tree中
? 的指针替换成了主键的键值。如图Fig.2所示：

Fig.2

? 这样就去除了Secondary B+Tree对数据页的依赖，而数据就变成了Clustered B+Tree(簇
? 索引对应的B+Tree)独占的了。对数据页的拆分及合并操作，仅影响Clustered B+Tree. 因此
? InnoDB的数据文件中存储的实际上就是多个孤立B+Tree。

? 一个有趣的问题，当用户显式的把主键定义到了二级索引中时，还需要额外的主键来做二级索引的
? 数据吗(即存储2份主键)? 很显然是不需要的。InnoDB在创建二级索引的时候，会判断主键的字段
? 是否已经被包含在了要创建的索引中。

? 接下来看一下数据操作在B+Tree上的基本实现。

- 用主键查询

? 直接在Clustered B+Tree上查询。

- 用辅助索引查询
? A. 在Secondary B+Tree上查询到主键。
? B. 用主键在Clustered B+Tree

可以看出，在使用主键值替换页指针后，辅助索引的查询效率降低了。
? A. 尽量使用主键来查询数据(索引遍历操作除外).
? B. 可以通过缓存来弥补性能，因此所有的键列，都应该尽量的小。

- INSERT
? A. 在Clustered B+Tree上插入数据
? B. 在所有其他Secondary B+Tree上插入主键。

- DELETE
? A. 在Clustered B+Tree上删除数据。
? B. 在所有其他Secondary B+Tree上删除主键。

- UPDATE 非键列
? A. 在Clustered B+Tree上更新数据。

- UPDATE 主键列
? A. 在Clustered B+Tree删除原有的记录(只是标记为DELETED,并不真正删除)。
? B. 在Clustered B+Tree插入新的记录。
? C. 在每一个Secondary B+Tree上删除原有的数据。 (有疑问，看下一节。)
? D. 在每一个Secondary B+Tree上插入原有的数据。

- UPDATE 辅助索引的键值
? A. 在Clustered B+Tree上更新数据。
? B. 在每一个Secondary B+Tree上删除原有的主键。
? C. 在每一个Secondary B+Tree上插入原有的主键。

更新键列时，需要更新多个页，效率比较低。
? A. 尽量不用对主键列进行UPDATE操作。
? B. 更新很多时，尽量少建索引。

05 – 非唯一键索引

? 教科书上的B+Tree操作，通常都假设”键值是唯一的“。但是在实际的应用中Secondary Index是允
? 许键值重复的。在极端的情况下，所有的键值都一样，该如何来处理呢？
? InnoDB 的 Secondary B+Tree中，主键也是此键的一部分。
? Secondary Key = 用户定义的KEY + 主键。如图Fig.3所示：

Fig.3

? 注意主键不仅做为数据出现在叶子节点，同时也作为键的一部分出现非叶子节点。对于非唯一键来说，
? 因为主键是唯一的，Secondary Key也是唯一的。当然，在插入数据时，还是会根据用户定义的Key