III: Small: Just in Time Datastructures

索引一直是任何数据库的关键组成部分。如今，“大数据”已经成为一个家喻户晓的术语，它们比以往任何时候都更加重要。索引使数据有条理，使您能够更快、更容易地获取任何信息，从流中的微博到银行账户中的钱。当然，有时很难弄清楚如何最好地保持数据的组织性。例如，在线社交媒体通常需要在一秒钟内处理超过十万条新消息。这是大量需要组织的数据，而且需要快速组织以跟上用户的需求。即时数据结构项目正在探索使索引更智能、更好地确定其工作的优先级以及更好地适应不断变化的工作负载模式的方法。具体来说，我们概括了一类称为自适应索引的索引数据结构。在自适应索引中，数据被组织为查询处理的副作用。在即时数据结构中，用户定义的策略指定如何根据查询和新数据转换索引。与即时编译器一样，索引针对当前呈现给它的工作负载进行了自适应优化。除了为即时数据结构的研究奠定基础之外，我们还在探索如何设计工作负载最优策略，以及如何使即时数据结构适应增量视图维护。

Indexes have always been a critical component of any database. Now that "big data" is a household term, they're more crucial than ever before. Indexes keep data organized, making it faster and easier for you to get at anything from the microblogs in your stream to the money in your bank account. Of course, it's sometimes hard to figure out how to best keep data organized. For example, online social media often needs to handle over a hundred thousand new messages in a single second. That's a lot of data that needs to be organized, and it needs to be organized fast to keep up with the users' needs. The Just-in-Time Data Structures project is exploring ways to make indexes smarter, better able to prioritize their work, and better able to adapt to changing workload patterns.Specifically, we're generalizing a class of index data structures called adaptive indexes. In an adaptive index, data is organized as a side-effect of query processing. In a just-in-time data structure, user-defined policies specify how an index is to be transformed in reaction to queries and new data. Like a just-in-time compiler, the index is adaptively optimized for the workload that is currently being presented to it. In addition to laying the foundations for research on just-in-time data structures, we are exploring how to design workload-optimal policies, and how just-in-time data structures can be adapted for incremental view maintenance.