III: Small: Just in Time Datastructures

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

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.