Indexing delight --thinking cap of fractal-tree indexes
?
8 likes?1,556 views
The document discusses various tree-based indexes for databases, including B-trees, Cache Oblivious Lookahead Arrays (COLAs), LSM trees, and fractal trees. It analyzes the performance tradeoffs between these structures for search, insertion, and space efficiency. A key point is that fractal trees can provide search performance similar to B-trees but with faster insertion by exploiting the block size of storage. The document also proposes using a block size-dependent fanout for ¦Å-B trees to achieve optimal performance.
Indexing delight --thinking cap of fractal-tree indexes
- 1. Indexing Delight Thinking Cap of Fractal-tree Indexes BohuTANG@2012/12 overred.shuttler@gmail.com
- 2. B-tree Invented in 1972, 40 years!
- 3. B-tree Block0 Block1 Block2 Block3 .... .... Block4 Block5 ..................................................................................... File on disk: ... Block0 ... ... Block3 ... Block5 ...
- 4. B-tree Insert Insert x Block0 seek Block1 Block2 Block3 .... .... Block4 Block5 ..................................................................................... File on disk: ... Block0 ... ... Block3 ... Block5 ...
- 5. B-tree Insert Insert x Block0 seek Block1 Block2 Block3 .... .... seek Block4 Block5 ..................................................................................... File on disk: ... Block0 ... ... Block3 ... Block5 ...
- 6. B-tree Insert Insert x Block0 seek Block1 Block2 Block3 .... .... seek Block4 Block5 ..................................................................................... File on disk: ... Block0 ... ... Block3 ... Block5 ... Insert one item causes many random seeks!
- 7. B-tree Search Search x Block0 seek Block1 Block2 Block3 .... .... seek Block4 Block5 ..................................................................................... Query is fast, I/Os costs O(logBN)
- 8. B-tree Conclusions ¡ñ Search: O(logBN ) block transfers. ¡ñ Insert: O(logBN ) block transfers(slow). ¡ñ B-tree range queries are slow. ¡ñ IMPORTANT: --Parent and child blocks sparse in disk.
- 9. A Simpli?ed Fractal-tree Cache Oblivious Lookahead Array, invented by MITers
- 10. COLA log2N ........... Binary Search in one level:O(log2N) 2
- 11. COLA (Using Fractional Cascading) log2N ........... ¡ñ Search: O(log2N) block transfers. ¡ñ Insert: O((1/B)log2N) amortized block transfers. ¡ñ Data is stored in log2N arrays of sizes 2, 4, 8, 16,.. ¡ñ Balanced Binary Search Tree
- 12. COLA Conclusions ¡ñ Search: O(log2N) block transfers(Using Fractional Cascading). ¡ñ Insert: O((1/B)log2N) amortized block transfers. ¡ñ Data is stored in log2N arrays of sizes 2, 4, 8, 16,.. ¡ñ Balanced Binary Search Tree ¡ñ Lookahead(Prefetch), Data-Intensive! ¡ñ BUT, the bottom level will be big and bigger, merging expensive.
- 13. COLA vs B-tree ¡ñ Search: -- (log2N)/(logBN) = log2B times slower than B-tree(In theory) ¡ñ Insert: --(logBN)/((1/B)log2N) = B/(log2B) times faster than B-trees(In theory) if B = 4KB: COLA search is 12 times slower than B-tree COLA insert is 341 times faster than B-tree
- 14. LSM-tree
- 15. LSM-tree In memory buffer buffer ... buffer buffer ... buffer ... buffer ... buffer ¡ñ Lazy insertion, Sorted before ¡ñ Leveli is the buffer of Leveli+1 ¡ñ Search: O(logBN) * O(logN) ¡ñ Insert:O((logBN)/B)
- 16. LSM-tree (Using Fractional Cascading) In memory buffer buffer ... buffer buffer ... buffer ... buffer ... buffer ¡ñ Search: O(logBN) (Using FC) ¡ñ Insert:O((logBN)/B) ¡ñ 0.618 Fractal-tree?But NOT Cache Oblivious...
- 17. LSM-tree (Merging) In memory buffer buffer ... buffer merge merge merge buffer ... buffer ... buffer ... buffer A lot of I/O wasted during merging! Like a headless fly flying... Zzz...
- 18. Fractal-tree Indexes Just Fractal. Patented by Tokutek...
- 19. Fractal-tree Indexes Search: O(logBN) Insert: O((logBN)/B) (amortized) Search is same as B-tree, but insert faster than B-tree
- 20. Fractal-tree Indexes (Block size) .... .... .... .... B is 4MB...
- 21. Fractal-tree Indexes (Block size) full .... .... .... .... B is 4MB...
- 22. Fractal-tree Indexes (Block size) full .... .... .... .... B is 4MB...
- 23. Fractal-tree Indexes (Block size) .. .. .. .. full .. ... ... ... .. .. .. .. .. .. .. Fractal! 4MB one seek...
- 24. ¦Å B -tree Just a constant factor on Block fanout...
- 25. ¦Å B -tree B-tree Fast ¦Å=1/2 Search Slow AOF Slow Fast Inserts Optimal Curve
- 26. ¦Å B -tree insert search B-tree O(logBN) O(logBN) (?=1) ?=1/2 O((logBN)/¡ÌB) O(logBN) ?=0 O((logN)/B) O(logN) if we want optimal point queries + very fast inserts, we should choose ?=1/2
- 27. ¦Å B -tree So, if block size is B, the fanout should be ¡ÌB
- 28. Cache Oblivious Data Structure All the above is JUST Cache Oblivious Data Structures...
- 29. Cache Oblivious Data Structure Question: Reading a sequence of k consecutive blocks at once is not much more expensive than reading a single block. How to take advantage of this feature?
- 30. Cache Oblivious Data Structure My Questions(In Chinese): Q1£º Ö»ÓÐ1MBÄڴ棬ÔõÑù°ÑÁ½¸ö64MBÓÐÐòÎļþºÏ ²¢³ÉÒ»¸öÓÐÐòÎļþ£¿ Q2£º ´ó¶àÊý»úе´ÅÅÌ£¬Á¬Ðø¶ÁÈ¡¶à¸öBlockºÍ¶ÁÈ¡ µ¥¸öBlock»¨·ÑÏà²î²»´ó£¬ÔÚQ1ÖÐÈçºÎÀûÓÃÕâ¸ö ÓÅÊÆ£¿
- 31. nessDB You should agree that VFS do better than yourself cache! https://github.com/shuttler/nessDB
- 32. nessDB .. ... ... ... .. .. .. .. .. .. .. Each Block is Small-Splittable Tree
- 33. nessDB, What's going on? .. .. .. .. .. ... ... ... .. .. .. .. .. .. .. From the line to the plane..
- 34. Thanks! Most of the references are from: Tokutek & MIT CSAIL & Stony Brook. Drafted By BohuTANG using Google Drive, @2012/12/12