Database systems research is an old and well-established field in computer science.udMany of the key concepts appeared as early as the 60s, while the core of relationaluddatabases, which have dominated the database world for a while now, was solidifiedudduring the 80s. However, the underlying hardware has not displayed such stabilityudin the same period, which means that a lot of assumptions that were made about theudhardware by early database systems are not necessarily true for modern computerudarchitectures.udIn particular, over the last few decades there have been two notable consistentudtrends in the evolution of computer hardware. The first is that the memory hierarchyudof mainstream computer systems has been getting deeper, with its different levelsudmoving away from each other, and new levels being added in between as a result,udin particular cache memories. The second is that, when it comes to data transfersudbetween any two adjacent levels of the memory hierarchy, access latencies have notudbeen keeping up with transfer rates. The challenge is therefore to adapt database indexudstructures so that they become immune to these two trends.udThe latter is addressed by gradually increasing the size of the data transfer unit; theudformer, by organizing the data so that it exhibits good locality for memory transfersudacross multiple memory boundaries.We have developed novel structures that facilitateudboth of these strategies. We started our investigation with the venerable B+-tree,udwhich is the cornerstone order-preserving index of any database system, and we haveuddeveloped a novel pointer-free tree structure for its pages that optimizes its cacheudperformance and makes it immune to the page size. We then adapted our approach toudthe R-tree and the GiST, making it applicable to multi-dimensional data indexes asudwell as generalized indexes for any abstract data type. Finally, we have investigated ourudstructure in the context of main memory alone, and have demonstrated its superiorityudover the established approaches in that setting too.udWhile our research has its roots in data structures and algorithms theory, we haveudconducted it with a strong experimental focus, as the complex interactions within theudmemory hierarchy of a modern computer system can be quite challenging to modeludand theorize about effectively. Our findings are therefore backed by solid experimentaludresults that verify our hypotheses and prove the superiority of our structures overudcompeting approaches.
展开▼
