The Most Elegant Search Structure | (a,b)-trees
HTML-код
- Опубликовано: 22 июл 2024
- An introduction to (a,b)-trees - definition, operations, usage.
------------------
Timetable:
0:00 - Fever dream?
0:28 - Introduction
2:04 - Basics
3:47 - Search
4:33 - Insertion
6:06 - Deletion
8:51 - Selecting (a, b)
10:36 - Usage
11:22 - Outro
------------------
Source code: github.com/xiaoxiae/videos/tr...
Music (in the order it appears in the video):
► The Big Ten by Blue Dot Sessions: app.sessions.blue/browse/trac...
► Cases to Rest by Blue Dot Sessions: app.sessions.blue/browse/trac...
► Maisie Dreamer by Blue Dot Sessions: app.sessions.blue/browse/trac...
► Thannoid by Blue Dot Sessions: app.sessions.blue/browse/trac...
Software used:
► Manim (animation software): github.com/ManimCommunity/manim/
► Kdenlive (video cutting): kdenlive.org/en/
► ffmpeg (audio/video processing): ffmpeg.org/
► OBS (audio/video recording): obsproject.com/download
► arecord (audio recording): linux.die.net/man/1/arecord
► sox (audio processing): sox.sourceforge.net/
► Inkscape (vector image editing): inkscape.org/
► Stable Diffusion (image generation): stablediffusionweb.com/
Social media:
► Website (for other things I'm up to): slama.dev/
► Patreon (if you'd like to support me): / ytoms
Thanks to Matěj Kripner, František Voldřich, Jakub Pelc, Hansen Pascal, Patrick Elsen and guys at @polylog7346 for valuable feedback.
------------------
[CZ] Martin Mareš: Průvodce labyrintem algoritmů:
pruvodce.ucw.cz/
[EN] Effect of Node Size on the Performance of Cache-Conscious B+-trees:
pages.cs.wisc.edu/~jignesh/pu...
[EN] frozenca/BTree: open-source C++ B-tree implementation:
github.com/frozenca/BTree
[EN] Other (a,b)-tree-related resources:
en.wikipedia.org/wiki/(a,b)-tree
en.wikipedia.org/wiki/B%2B_tree
en.wikipedia.org/wiki/B-tree
Your videos are incredible! Loved the simplicity and the animations. Source code of the video is a big plus!
i clicked on this curious if there was something nicer than a b+tree 😭. sticking around bc the quality is good
Very vell explained. Thank you for the video.
OMG, This video is so good. So underrated. I am watching this after struggling to understand B-tree several times and oh god you're so good.
Wow! The quality this video is incredible! And it remains true for every video on your channel. Thank you so much for it!
I’m glad I found your channel.
What a fantastic explainer! Quality is sublime! Well done!
the amount of artifacting from youtube compression makes me feel like an ai watching a video. Ty for the nice video!
thanks for this beautiful video ^_^
This is really cool
Thank you for your concern, yes I am indeed having a nice day :)
new sub here . good work bro keep going !!
We learnt in the university the AVL trees, and finding out there is a much better solution hurts a little bit : )
B+ trees are used in nearly every database and filesystem.
well animated videos are so helpful. Can you please keep making them until I graduate? Please.
hope you make video about Fenwick tree with this animation
How do you edit these videos?Any tutorial?
All of the software I use is free and linked in the description. I also wrote a series of tutorials on how to start animating with Manim (how most of the animations in the video are done): slama.dev/manim/introduction/
Does anyone know what happens when you can't merge or steal? Stealing relies on an adjacent node having an extra and merging relies on the above node having an extra. What if neither of them have any extra to spare?
The node above doesn't need to have an extra key. If it doesn't, we merge and have to fix the condition one layer above, that's why we prefer to steal (which doesn't propagate up).
@@YTomS that makes sense! Thank you!
whats the name of the music between 0:28 and 2:00, it doesnt seem to be one of the ones listed in the description
It is - Cases to Rest. The UI on the website is, however, quite unintuitive and just pressing the play button plays a random track (you have to press on the name).
Should I avoid the subscribing? Definitely, no! 😂
Really well explained video 👍
Very funny!
you think rotations are more complicated than this?
It's really a personal preference, but a-b trees feel cleaner to me because all I have to remember when adding is "if too many then split" and when removing is "if too little then steal / merge".
AA trees enter chat
In "Usage" section u said c++ n java technically use Red-Black trees to implement maps and sets, but they are actually a-b trees
How is a red-black tree same as a-b tree?
There is a mapping between a 2-3 (or 2-4, based on definitions) tree and a R&B tree. I didn't want to mention it in the video since I'd have to define what an R&B tree is and it doesn't add too much to the video.
Imagine the red nodes / red-linked nodes as actually being part of their parent black node.
If you're using red-black trees where black nodes can only have one red child, that gets you a 2,3 tree.
If you're using red-black trees where black nodes can have up to two red children, that gets you a 2,4 tree.
@@hemerythrin Thankyou!
Confusing as hell, what do the blank Squares mean? No nodes? Is this then a always 2 level tree?
can you make a tutorial to make vidios in this style, is so sexy
U speak too fast. Ok for a netflix movie or youtube entertainment video, but high speed talk in a technical video increases the # of rewinds to re-listen the sentences a few times. No?
It's definitely better compared to my older videos, but I agree that it still isn't ideal. I'll try to slow the next one down :).
@@YTomS If it helps, your speed is the one I target when I manually change it for other slower videos :))
I don't think he spoke fast, just should've used more words to give us time to think and understand the operations
@@pratikkore7947 Or my grasping power is weaker :)
There are captions
Your videos are the next beautiful thing (I mean "wonderful") I have found beside Dr. Bartosz Milewski's series on Category Theory!
How about webinars? I would definitely sign up for it.
Keep up the great works and speak slower! 🫡