索引的可扩展性和并发性探讨 Indexing for High Throughput and Sca
数据类型、数据操作和应用环境等诸多因素不断驱动着新型索引的设计。数据库系统需要对移动对象、时间序列和字符串等新型应用提供支持，这也导致新型索引的发明。但是，当前主流的商业数据管理系统主要支持B+树(B+-tree)、R树(R-tree)、哈希表(hash table)和位图(bitmap)的变种。这主要是因为一旦一种新索引被引进，许多其他组件，诸如查询处理器，并发控制和缓存管理器不得不被修改——对大多数系统来说，这是一个代价高且担风险的决定。
索引在设计方面应该简洁和精确，在性能方面应该高效、健壮且可扩展。不幸地是，许多设计经常顾此失彼，例如移动对象数据库有较高的更新和查询负载，索引设计需要支持并发操作(concurrent operations)；另外，索引需要存储在磁盘上则是为了在每台机器上支持许多应用和并发用户。任何设计复杂的索引都不太可能很好地扩展，因为它们维护代价昂贵，而且需要配置很多系统参数，如查询类型，查询分布，数据分布，页大小，等等。
索引的基本思想是将数据划分成组，以便让每个组可以被存储到一个物理页（典型地是4K字节，但是现在大多数系统是8K字节）。在划分过程中，可以使用多层结构，每一层都是划分成几个区间范围，越小层的区间划分越细。在遍历的过程中，效果是与在地图上搜索街道是一样的：从大的坐标方格到更小的坐标方格，再到指定的页。这允许我们高效定位查询的数据项。B+树和R树就很好地抓住了该本质，且两类索引都是动态和高效的。对于B+树，经过较好测试的B链树(B-link)并发控制被用来支持并发访问和高效总处理能力。同样地，R链树(R-link)也被用于R树。
索引本身是有代价的。索引必须为每次修改而更新。因此，当索引促进了快速检索，索引可能导致在更新上不必要的延迟，尤其是当索引建立在每个表或数据集上面。在更新期间的锁操作将引起读操作的等待，从而降低了搜索效率。
索引设计可能带来的一些问题：
1）预处理：已经有人建议对数据进行预处理，诸如插入操作，优化索引。预处理可以改善检索效率，但也引起大部分索引被锁住，带来并发检索的复杂性。
2）多个索引结构的使用：既然多个索引被用来索引数据集的不同属性，对任一个数据项的更新在多个索引上必须是同步发生的。在某些情况下，索引（更新的一条路径）必须是同时被遍历和锁住。
3）多个结构的使用：多个结构的使用将使得并发控制复杂化。例如，有人提出，在内存中存放“热点”数据项，对于“冷门”数据项则使用基于磁盘的索引。数据同步导致开销，且不可能有效地决定移动数据项如何从一个索引转到另外一个索引。
4）代价较高的划分函数的使用：有些函数在描述数据上能够提供很好的精度。索引结构应该�**恕富惴�(filter-and-refine)的一部分或者方便其他操作的执行，诸如join。因此，该部分的主要目的是尽可能更快地过滤那些假阳性的部分。代价高的划分函数虽然能够减少过滤的代价，但这样的函数更适用于静态数据集，难以较好地在动态环境下扩展，因为这样的环境下，更新和新的插入操作是非常普遍的。
5）内存索引：大多数人可能认为索引足够小可以放进内存。如果系统仅支持少数几个应用和并发用户，这种观点是正确。在大多数系统中，缓存被划分以便用于不同的目的，系统和其他的代码消耗大量的内存。此外，既然内存是易变的，其他的机制也是必须的以便确保更新的一致性。对于基于内存的索引，L2高速缓存优化是在设计中主要考虑的因素之一。
6）页大小：更小的页大小意味着每页更少的记录，且可以提供更佳的优化效果。然而，页大小通常是由系统决定，而不是由索引设计者所决定。此外，更小的页大小导致更高的索引层次和引起更多的随机读的I/O操作。
上述问题主要是由以下因素引起：缺乏并发性的考虑，混淆索引结构的用途，和缺乏对硬件和操作系统环境的理解。毫无疑问，索引机制仍然是快速有效地减少搜索代价的最佳方式。建立新索引总是比发明新查询处理策略来得容易。这也解释了索引技术的快速发展。事实上，因为索引影响了缓存管理策略，查询优化和处理策略，并发控制和恢复，没有哪一个通用数据服务器能够支持和维护很多种索引。
综上所述，索引如果没有合理地被设计，将变成一种负担，而不是一种加速机制。因此，直到今天，B+树，R树和哈希表仍然是主要的索引结构。
http://ooibc.blog.163.com/blog/static/103968235200911100195944/
