Tokutek
57 Pages
English

Tokutek

-

Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Description

®Fractal Tree Technology Overview The Art of Indexing Martín Farach-Colton Co-founder & Chief Technology Officer Not all indexing is the same B-tree is the basis for almost all DB systems • Data structure invented in 1972 • Has not kept up with hardware trends Works poorly on modern rotational disks‣ Works poorly on SSD‣ Fractal Tree Indexes is the basis of TokuDB • Scales with hardware • Fast Indexing ➔ More Indexing ➔ Faster Queries • Great Compression • No Fragmentation • Reduced wear on SSDs The Art of Indexing ® How do Fractal Tree Indexes outperform B-trees? How do Fractal Tree Indexes outperform B-trees? First, some facts about storage systems Storage is quirky Hard disks are slow for random I/O but fast for sequential I/O Difference causes problems like fragmentation, ... The Art of Indexing ® Storage is quirky Hard disks are slow for random I/O but fast for sequential I/O SSDs are fast for Difference causes problems random I/O but expensive for like fragmentation, ... sequential. Garbage collection causes artefacts: increased wear, write cliffs...

Subjects

Informations

Published by
Published 27 June 2013
Reads 66
Language English
Document size 1 MB

®Fractal Tree Technology Overview
The Art of Indexing
Martín Farach-Colton
Co-founder & Chief Technology OfficerNot all indexing is the same
B-tree is the basis for almost all DB systems
• Data structure invented in 1972
• Has not kept up with hardware trends
Works poorly on modern rotational disks‣
Works poorly on SSD‣
Fractal Tree Indexes is the basis of TokuDB
• Scales with hardware
• Fast Indexing ➔ More Indexing ➔ Faster Queries
• Great Compression
• No Fragmentation
• Reduced wear on SSDs
The Art of Indexing
®How do Fractal Tree
Indexes outperform
B-trees?How do Fractal Tree
Indexes outperform
B-trees?
First, some facts about storage systems Storage is quirky
Hard disks are slow for
random I/O but fast for
sequential I/O
Difference causes problems
like fragmentation, ...
The Art of Indexing
®Storage is quirky
Hard disks are slow for
random I/O but fast for
sequential I/O
SSDs are fast for Difference causes problems
random I/O but expensive for like fragmentation, ...
sequential.
Garbage collection
causes artefacts: increased
wear, write cliffs...
The Art of Indexing
®Storage Big Reads and Writes
Big I/Os
The Art of Indexing
®QStorage Big Reads and Writes
Hard Disks: No
Fragmentation
Big I/Os
The Art of Indexing
®QStorage Big Reads and Writes
Hard Disks: No
SSDs: Less Garbage Fragmentation
Collection & Wear
Big I/Os
The Art of Indexing
®QStorage Big Reads and Writes
Hard Disks: No
SSDs: Less Garbage Fragmentation
Collection & Wear
Big I/Os
But you only get the goodies if
each I/O has lots of new bytes
The Art of Indexing
®Q