8 Key Data Structures That Power Modern Databases

Weekly system design newsletter: bit.ly/3tfAlYD
Checkout our bestselling System Design Interview books:
Volume 1: amzn.to/3Ou7gkd
Volume 2: amzn.to/3HqGozy
LSM tree video: • The Secret Sauce Behin...
Other things we made:
Digital version of System Design Interview books: bit.ly/3mlDSk9
ABOUT US:
Covering topics and trends in large-scale system design, from the authors of the best-selling System Design Interview series.

[@ByteByteGo]

Subscribe to our weekly newsletter to learn something new every week: bit.ly/3JFtDUK

[@vamsyrraju]

What software is used to create these presentations :)

[@jonathangamble]

Would like to see more on how these are implemented!

[@clem_grim]

I recommend the book "Database internals" for this

[@alexgregory5583]

This professor is amazing for explaining a lot of these: kzbin.info/www/bejne/l4vNiqVubNdkmJo&ab_channel=AbdulBari

[@ilonachan]

that'd probably be a whole lecture, and I'm here for it

[@experiment0003]

@@ilonachan That'd be more than a lecture. That would be a 4-month course, at the least! And that is assuming you have a solid handle on CS fundamentals and data structures.

[@woolfel]

like other commenter stated, that would be a multi-month course to get started. To really understand it each of the indexes and how to implement it efficiently, you'd have to spend 1-2 years. If you're short on time, one way to learn how to implement these is to read the source code for postgres, mongodb, cassandra, derby, or sqlite. You can look at the history of those files to see how the implementation evolved.

[@ejm110]

after a minute, I do not understand anymore but still watched because of simple cool animation and concise short explanation on each one.

[@markgreen2170]

yes, each graphic is probably, at least a month of study ...for me at for me anyway, lol!

[@ViktosB]

Amazing source of tech insights. Thank you for your effort.

[@anuzis]

Really appreciate the effort that goes into making these videos so concise and informative. Glad I found the channel & looking forward to your next episode!

[@samirelzein1095]

Amazing job, concise, well presented, right to the point...

[@DK-ox7ze]

It will be great if you can come up with a video which maps use cases to DBs. Like which type of DB is best suited for which use cases? Covering popular DBs like RDBMS, Document DB, Key value, Column family DBs, colum oriented DBs, Map reduce, and so on.

[@LawZist]

He already did this kind of video ;) kzbin.info/www/bejne/oZzId3hsnreZg68

[@faroukfaiz8396]

He already did: "How To Choose The Right Database?".

[@DK-ox7ze]

@@faroukfaiz8396 Yes but it doesn't cover which database to choose for which scenario. He has only outlined the pros and cons of migrating to a new db

[@daydrivver2074]

Gotta be honest your content is rock solid already ordered a copy of your book, can we get a video on the solid design pattern? Kinda like the way your animations explain these highly difficult to learn pattern. Thanks!

[@big6226]

Thank you, sir Your presentation is great.

[@jinrivers9834]

These animations are really awesome. I'm very curious about how they were created

[@revenez]

Amazing visual representations, thank you!

[@Openspeedtest]

How do you animate your videos? Your animations are super cool!

[@boolve]

I live those graphics. Not boring to look at, when listening is boring.

[@MisFakapek]

Nice one, but would really like to see some additional videos in this topic - potentially with more exotic algo and data structures.

[@DigitalAlligator]

Comment section as expected, all appreciated the wonderful work

[@ThePiyushD]

Like the animations you create. Can you share what tools you use ? Probably make a video on that :)

[@erfannariman]

These video's are amazing, anyone got a clue which program is used to make them?

[@dibll]

Would like to see more details on these data structures!

[@Pradeepch21]

Please add detailed videos for these algorithms

[@bazoo513]

Well, you merely _mentioned_ those structures. You cannot call this "discussing" them.

[@mpateltech4127]

We would like see detail level video on each item….. with wonderful presentation

[@chrisliewjy]

Amazing stuff as always

[@SingaraveluS]

Great videos that helps me to understand and enables to further understand what my developers explaining to me. I am from financial services. Curious to know what animation tools are being used, will be useful for our financial services presentations.

[@johnathandeckert]

I'm curious as well. Great clean visuals.

[@sumonmal009]

very important concepts

[@yoshiakisano3920]

What kind of software was used to make the animation? so fascinating

[@TruSktr]

Can you please cover r-trees and spatial databases? That would be awesome!

[@richardjohnson8009]

Very well presented! Thanks

[@clef6167]

Skiplist, hash index, SSTable, LSM tree, B-tree, Inverted index, Suffix tree, R-tree

[@Pikachu-oo5ro]

I wish your videos had 38 million views.

[@Cyberfoxxy]

Love the visuals

[@nkbuaa]

would like to see videos on big data, like spark, hdfs, hive etc..

[@sandybeaches]

I LOVE your videos. This is blowing my mind. I'm even an app developer and security specialist and I've never heard of these data structures. This is why I subscribe to ByteByteGo.

[@reromsp]

Looking for more videos from you on Data structures and Algorithm

[@johannjohannes7214]

While this is a starting point to research those data structures, it's hardly more than that

[@ksb2112]

I would be interested in seeing what data structures graph databases such as Neo4J, etc. use.

[@mohammedesmail2655]

Thank you. Can you tell what tool you are using to do this presentation 😊

[@plasmaguy5]

Awesome video thanks

[@sridevavkb]

What ever it is we are happy.

[@dianpriyambudi]

Thank you! ❤

[@bhadrakshbhargavaiiitt742]

I want to create my own DBMS. How can I go about it?

[@rajvis16]

Please do a video on inverted index

[@sortof3337]

Can you also make videos on wavelet trees?

[@harirambj]

Can you please explain all 8 Types in detail video

[@prasantkumar7693]

Thank you,👏

[@pedrojesusrangelgil5064]

Nice video! what about in memory databases like sap hana? thks for sharing!

[@romannasuti25]

Those typically use modified forms of B-tree, R-tree, and structures like red-black trees commonly used as the memtable for LSMs. The in-memory approach either focuses on extreme OLTP performance like the SILO research database and resulting LineairDB embedded database by NTT Data, or in the case of SAP HANA, uses efficiently compressed in-memory columnar B-tree storage for blisteringly fast columnar reads for extremely fast-processing aggregations.

[@romannasuti25]

Unless tied to the SAP ecosystem, I'd say stay away from HANA and use a more fitting system: A great open source fault-tolerant OLTP system like FoundationDB, YugabyteDB, or DGraph with modification streaming to a columnar fast-response OLAP system like Apache Druid, previously memory-only but now works on disk too.

[@520srikanth]

Awesome

[@alquinn8576]

Al Quinn keeps his data in the best of all databases: MS Paint 🖌

[@johnmancini3080]

Does anyone know what software he uses to build these videos?

[@gillall4828]

10/10

[@Bob94390]

I assume that these data structures are important. The presentation was almost useless, though; far too little was said about how to use these structures, what advantages they have, how they are implemented and so on.

[@theVtuberCh]

No Hash Mapped Array Tries?

[@DK-ox7ze]

Redis is a key value DB, so Hash index makes perfect sense. But I am wondering why Skip list is used in it?

[@DK-ox7ze]

@@sansmoraxz Why is sorting required when we can access key values in O(1) time?

[@krajekdev]

Redis can hold a data structure (for example mentioned sorted under a key) and allows to operate on these data structures without downloading them. That is when other data structures come it, they implement the data structures(lists, sets etc).

[@DK-ox7ze]

@@krajekdev The values associated with a key are user defined, so it's up to the user to choose what data structure it wants in the key's value. Why should Redis dictate that?

[@krajekdev]

@@DK-ox7ze Because we are talking about Redis data structures. As an example, take a look at the SADD command. It operates on a set (internal Redis data structure, not user-defined structure). Other commands operate on lists, hashes etc.

[@llothar68]

And the implementation hell opens its gate once we can't use this structures in memory but have disk based representations.

[@adorinadorin]

I need more details. Here it is too short and shallow. Could be just a matrix instead without sacrificing content.

[@gus473]

👍 1,000th "Like!" Thanks! 😎✌️

[@developer_hadi]

cool

[@jaime7295]

Make a video of rtrees

[@kishoreytc]

You don't have to flex like that.....

[@ivanborsuk1110]

i doubt anything of this powers modern databeses database table is just unsorted array of c structs if you create an array of pointers to rows of table, you can qsort that array of pointers by writing appropriate comparators now you have indexes bsearch them thats all you need to have fun

[@irrelevant_noob]

That might've been the case some time ago, but the video seems to include cases like document storage and analysis, and high-volume tables (millions of rows)... Your approach doesn't seem to be able to handle those needs. 🤓

[@Kyoz]

🤍

[@olsuhvlad]

1 In the beginning was the Word, and the Word was with God, and the Word was God. 2 The same was in the beginning with God. 3 All things were made by him; and without him was not any thing made that was made. 4 In him was life; and the life was the light of men. 5 And the light shineth in darkness; and the darkness comprehended it not. (Jn.1:1-5) 9 That was the true Light, which lighteth every man that cometh into the world. 10 He was in the world, and the world was made by him, and the world knew him not. 11 He came unto his own, and his own received him not. 12 But as many as received him, to them gave he power to become the sons of God, even to them that believe on his name: 13 Which were born, not of blood, nor of the will of the flesh, nor of the will of man, but of God. 14 And the Word was made flesh, and dwelt among us, (and we beheld his glory, the glory as of the only begotten of the Father,) full of grace and truth. (Jn.1:9-14)

[@irrelevant_noob]

Out of the millions of books available to us today, you're stuck on the one that was put together millennia ago by warring tribes-people... 🙄

[@handsomeman-pm9vy]

And the Great Pumpkin arrives every Halloween to renew our spirit.

[@olsuhvlad]

@@irrelevant_noob You are mistaken. This is a New Testament book. What tribes were at war? You are now at enmity against the followers of Christ, and at enmity against Himself. Is there a creation watcher book? :) - From millions of human delusions... :) You just think you're wise. :) - In their eyes. You would have self-criticism and more arguments are not enough. So, empty lyrics - show yourself, or reassure yourself that you are supposedly on the right track. By the way, which of the millions of human books deceives you more according to your sinful heart? :)

[@irrelevant_noob]

@@olsuhvlad oh so you've gone past the first edition (OT) and went with the one with stories from the rebellious tribes, that couldn't afford to be fully-at-war anymore after they were conquered by rome. great improvement. /s And do you think i care about being "at enmity" with your imaginary friend, why, again? He seems to be occupied with plenty of other stuff, presumably napping, doesn't take time for anything anymore. Hasn't done it for millennia. Can't answer most of the rest of it, since they're pretty incoherent. Try writing them in your own language, an auto-translation might work better for getting others to understand what you're trying to tell us. More than what? I've gone through a period where The Three Musketeers was the bomb, then there were some Jules Verne, Agatha Christie, Isaac Asimov... That's the beauty of being open to stuff -- there's plenty to stop one from getting stuck in a single dull place.

[@olsuhvlad]

@@handsomeman-pm9vy 18 For the wrath of God is revealed from heaven against all ungodliness and unrighteousness of men, who hold the truth in unrighteousness; (Ro.1:18) 28 And even as they did not like to retain God in their knowledge, God gave them over to a reprobate mind, to do those things which are not convenient; 29 Being filled with all unrighteousness, fornication, wickedness, covetousness, maliciousness; full of envy, murder, debate, deceit, malignity; whisperers, 30 Backbiters, haters of God, despiteful, proud, boasters, inventors of evil things, disobedient to parents, 31 Without understanding, covenantbreakers, without natural affection, implacable, unmerciful: 32 Who knowing the judgment of God, that they which commit such things are worthy of death, not only do the same, but have pleasure in them that do them. (Ro.1:28-32)

[@BronkoBanane]

Without use cases and time complexity comparsion the Video is useless:/

[@kevinsmirnov264]

useless

[@hamodeyDooba]

Great content What tools do you use to create this content and the animations Thanks❤

[@catfishdiver2518]

I am interested in this as well. The Visual aspects of your presentations are just as insightful as your concise verbiage!

[@cloudfumes7367]

Can u please create video how you do animations helpful for many you tubers

[@tomgates316]

Would like to see info on hierarchical databases and the various implementations. HIDAM, HDAM, Logical Linking. How HDAM is a 1 I/O access.

[@qsquared8833]

Which one is used in MS SQL? B-Tree?

[@ReflectionOcean]

!. Skiplist (probabilistic data structure to implement a Sorted Set for efficient lookup, insertion and deletion) ~ B-Tree 2. Hash index: key - hash function -> bucket 3+4. SSTable + LSM Tree (NoSQL) 5. B-Tree (Balanced Tree): Internal nodes to store keys and leave nodes to store actual data (DBMS) 6. Inverted Index: word -> document (Elastic Search) 7. Suffix Tree (Trie): search box 8. R-tree

[@Wingly113]

Which category does the Vertica Analytic database falls into? And what do you think about the architecture of Vertica database? The concept of logical and physical schema in Vertica is truly unique and beneficial for performance and availability.

[@romannasuti25]

Vertica, as far as I'm aware, uses a modified per-column B-tree setup along with bitmap indexes. The column orientation allows for efficient compression and resultant fast bulk reading for analytics workloads, but makes OLTP-type modification and access impractical. An attempt at an HTAP database on these same principles is SAP HANA, which increases the aggressiveness of compression with smaller "chunked" columns residing in memory with a Postgresql-like pending write hold which gets flushed during dips in workload or when many writes are pending on one chunk.