How Databases Work

Huiqi and I use the analogy of a book to explain about how database work. We explore some very interesting data structures and algorithms that are used in the database.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : we're going to talk about how a database
00:02 : works right
00:03 : i thought i'd bring along this book
00:05 : because
00:06 : it i think a book is a good analogy for
00:09 : how a database works okay
00:11 : there's a couple of things that this
00:14 : book
00:14 : is similar to a database one way is
00:18 : the content of the book is divided in
00:21 : chunks
00:22 : where a chunk is a page so
00:25 : every page has the same size right so
00:29 : even though you can think of all the
00:31 : content of the book is just
00:32 : one long contiguous stream of
00:36 : words at the end of the day you still
00:38 : have to divide them up into pages
00:40 : right and so there's a discrete number
00:43 : of pages
00:44 : the database works the same way the
00:47 : all of the data within the database are
00:50 : stored
00:51 : on pages they also call them pages
00:54 : sometimes they
00:54 : call them blocks as well let's say um
00:58 : the database has a whole bunch of
01:00 : records
01:03 : like each row is a record uh
01:07 : yes each row of a database table
01:10 : let's say is a record this can be seen
01:13 : as
01:14 : a long contiguous stream of information
01:18 : what the database is going to do is
01:21 : store it
01:21 : into fixed sized pages so maybe
01:25 : a page is like this
01:28 : there's many pages that are needed to
01:32 : contain all the of the stuff how does it
01:35 : know which
01:35 : page yet yep so
01:39 : good question uh the reason
01:43 : we do this separate things into fixed
01:45 : size blocks
01:46 : is because it's it's much more
01:50 : predictable
01:51 : to make assumptions about how long it
01:54 : takes
01:55 : to save a fixed size chunk onto the disk
01:59 : another reason is because there are
02:02 : actual
02:03 : meaningful sizes the physical
02:06 : hard drives that we use they have
02:10 : actual physical disk sector sizes
02:13 : which i believe is like 512 or something
02:16 : that's the smallest
02:17 : unit of data you can read or write from
02:20 : a disk if you want to read anything at
02:22 : all
02:22 : you at least have to read that much
02:26 : and also operating system use this
02:29 : concept of fixed size blocks in the
02:32 : workings of the operating system
02:34 : as well so when you're reading a file
02:37 : from the disk
02:38 : um the operating system is gonna
02:42 : make one page allocate one page in the
02:45 : operating system
02:46 : and put stuff in it and then give it to
02:48 : your program so it's like
02:50 : might as well use pages to match up with
02:53 : what the operating system is doing
02:56 : um your question is how do you know
03:00 : where to put it how do you know like
03:02 : what record goes on yeah what page
03:05 : right so another thing about the book
03:09 : is that it's got this table of contents
03:12 : where is it yeah
03:13 : this table of contents is like your
03:16 : primary index
03:18 : right the primary index is basically
03:21 : laying out for you
03:23 : the order of the content in the book
03:26 : in the primary way that it's organized
03:29 : right
03:31 : in a database that's equivalent to a
03:33 : primary key
03:34 : of a table if you're looking for a
03:37 : particular section you can
03:38 : either use the section number or the
03:40 : page number to
03:42 : to find the actual page um
03:46 : which kind of answers your question
03:49 : about how do you
03:50 : know where the where the
03:53 : record is uh given like you want
03:57 : a particular record and you know the
03:59 : identifier for the record
04:01 : if you don't know if you don't know
04:03 : anything about the database look through
04:05 : the table of contents
04:06 : which is your primary key i guess when
04:09 : you're dealing with
04:10 : an application that reads from a
04:12 : database so
04:14 : you can also just list all of the things
04:17 : or you or you already know a primary key
04:21 : if you already know a primary key ob you
04:23 : already know the section
04:24 : that you're looking for i want to learn
04:26 : about greedy algorithms
04:28 : so you look it up in the table of
04:30 : contents and then that's your page
04:32 : number
04:32 : okay and which is exactly what the
04:35 : database has
04:36 : as well the database also is going to
04:38 : have a primary index
04:41 : um the primary index of a database
04:44 : also has to fit into these pages as well
04:47 : so just like a book okay so there are
04:50 : pages
04:50 : that are you know dedicated to storing
04:54 : the
04:54 : table of contents or the primary index
04:57 : and then and then the database also has
04:59 : to keep track of where those pages are
05:01 : versus the pages that store actual
05:04 : content
05:05 : there's also a secondary index in the
05:07 : back of the book
05:08 : now there it is
05:11 : so yeah so you the secondary index
05:15 : is a sorted list of the concepts
05:19 : that are that are notable that were
05:22 : covered in the book right so you could
05:24 : look through the secondary index and uh
05:28 : in the database the secondary index
05:30 : would be
05:31 : something like index for foreign key or
05:35 : just a title
05:36 : like you want to be able to search by
05:38 : the title
05:39 : and so you put an index on the title and
05:42 : that would be your secondary index so a
05:44 : database can have
05:45 : a number a number of secondary indexes
05:48 : for a given table
05:50 : what what if your index everything what
05:52 : will happen
05:54 : is that index okay really fast
05:57 : uh okay good question
06:01 : so we have a user table uh
06:04 : we have four columns and we were saying
06:07 : basically like should we just
06:09 : index all the columns so that searching
06:12 : for the user by any column would be
06:14 : fast what that amounts to is you end up
06:17 : creating
06:18 : one secondary index for each column
06:22 : similar to the one at the back of the
06:23 : book so you just have
06:25 : three of those okay instead of just one
06:28 : but the cost of doing that is you have
06:31 : actually there's some
06:33 : some work that need to be done to
06:36 : maintain the indexes
06:39 : every time you update a user
06:43 : or any number of users or you add a user
06:45 : delete a user
06:47 : modify information about the user you
06:49 : need to
06:50 : keep those indexes updated that's not a
06:53 : problem for the book
06:55 : because the book does not change right
06:58 : for
06:58 : database that is a problem and
07:02 : and let's think about now how the
07:05 : database
07:06 : maintains those indexes if the database
07:10 : um store the indexes
07:13 : this is one of the secondary indexes
07:16 : let's say this was the secondary index
07:18 : for
07:18 : username which means
07:22 : well if you uh add a new user it has to
07:26 : add an entry in this index um you you
07:30 : go alphabetically to find where
07:33 : the email address of the new user should
07:36 : go in and you actually have to make room
07:39 : so
07:39 : if it's sorting this format you have to
07:41 : push all the stuff
07:43 : exactly so like the user is emily we're
07:46 : gonna
07:46 : stick it somewhere here some somewhere
07:50 : in here
07:52 : we have to make room to put emily in
07:54 : here all the entry after it
07:56 : has to shift down in this page
08:00 : and that means all these pages have to
08:02 : change
08:03 : and this is a pretty big index so that
08:06 : that's actually
08:07 : pretty expensive what if they use a
08:10 : linked list
08:12 : will that work yeah that that would be
08:14 : cheaper okay so yeah
08:15 : now now we're talking about choosing
08:17 : data structure right
08:18 : the design of the database is uh very
08:21 : much reliant on
08:23 : like the the data structures the
08:25 : algorithms that you use
08:27 : how are we going to store the index
08:30 : we could use an array and if we use an
08:33 : array we'll have to find the place to
08:35 : insert it and then
08:37 : once we find that like all the
08:39 : subsequent
08:40 : entries will have to shift one over just
08:42 : to make room right
08:43 : for the new entry what was the big o
08:47 : of this operation uh
08:50 : it's right where where uh this is n
08:54 : adding it's n yeah it's big o of n
08:57 : because
08:57 : the first just finding this place
09:00 : uh finding this place is log n because
09:03 : you can do binary search
09:04 : there so uh so
09:08 : but the shifting is n right and then so
09:10 : that the time is like
09:12 : n plus log n and because log n is small
09:15 : compared to n
09:16 : we don't care about this guy so we just
09:19 : say this is a big o of
09:20 : n um let's do a linked list
09:26 : you don't need to shift exactly
09:29 : you don't need to shift in the length
09:33 : but you still have to find it exactly so
09:36 : in a linked list you you're gonna find
09:39 : where to
09:40 : insert the entry uh and then
09:44 : but you don't have to do this shifting
09:46 : thing
09:48 : because you can just change this pointer
09:50 : to point to the new thing
09:51 : right that's the new thing uh point uh
09:54 : and then
09:55 : you have the new thing point to the next
09:58 : thing
09:58 : in here so uh what's the big o of
10:02 : this insertion so this is a linked list
10:05 : well that's
10:05 : one thing well
10:08 : you when you find it then you can you
10:11 : have to go through everything to find it
10:13 : exactly so the the the words
10:17 : the array we could find it in login time
10:19 : yeah with the linked list we have to
10:21 : find it in
10:22 : end time now so there's still n
10:26 : n plus big o of one which uh we still
10:29 : have n
10:30 : but this it's probably going to be
10:33 : better because the copy operation is
10:35 : going to be more expensive
10:37 : for just looking through so long list
10:39 : version would
10:41 : be better than this version but still
10:43 : it's still
10:44 : big of than okay so obviously we want
10:48 : something
10:48 : that's better there's two better
10:51 : strategies
10:52 : one is the hash table
10:55 : another one is the tree um
10:59 : wait the the hash table doesn't
11:02 : really work now that i think about it
11:04 : hash table doesn't work with
11:06 : ordered values okay
11:13 : let's just talk about the tree this is
11:15 : sorted alphabetically
11:17 : uh but we don't have to
11:21 : this is not the only way to sort things
11:23 : we can
11:24 : think of sorting as in things are sorted
11:28 : into bins oh i know the tree you're
11:32 : talking
11:33 : so so one way is like we can say uh
11:35 : we're gonna divide up
11:37 : the index into 26 spin
11:42 : one for each letter in the alphabet
11:48 : spoke etc into z
11:52 : and then all the a's are in
11:55 : a bin oh and then that's the second
11:57 : letter
11:58 : and all the b's are in a
12:02 : separate bin other c's in a separate bin
12:06 : so i know emily is gonna be in the even
12:10 : and if the even was
12:13 : just an array then i could go do the
12:15 : same thing as i would do here
12:17 : to the even but we don't have to stop
12:20 : here
12:21 : because we could say hey you know what
12:24 : that for
12:24 : i'll i'll put this divide this up into
12:27 : bins
12:28 : for the second letter okay gotcha we
12:31 : don't have to stop here
12:32 : so i can do a b c d all the way
12:36 : until z and now we could keep doing this
12:39 : for several levels okay and that will
12:42 : make the
12:42 : search really fast right because if
12:45 : if you do three level even three levels
12:48 : or four levels
12:49 : you can imagine well at the end you
12:52 : don't have that many things left
12:53 : right that are all start with e m and
12:56 : i um so
13:00 : this is why the tree works
13:04 : and this is how you can conceptualize it
13:07 : but uh but this scheme using the
13:10 : alphabetic letters
13:11 : that's a very static scheme as in
13:15 : uh well i'm organizing things by the
13:19 : alphabet letters
13:20 : like this but it it doesn't have to be
13:22 : like that
13:23 : because this may not be the most
13:25 : efficient way to divide things up
13:27 : maybe your system has a lot of ease and
13:30 : no a's at all oh okay and then i'm kind
13:33 : of
13:34 : wasting space over here so a more
13:37 : dynamic scheme
13:38 : following the spirit of this but without
13:42 : having it be predetermined like how
13:46 : the notes are to be organized
13:49 : and that's what a binary tree does and
13:51 : it's also what a
13:52 : b tree does i think it's easier to
13:56 : just talk about the binary tree for for
13:58 : this purpose
14:00 : the b3 is a little more complex this is
14:02 : a valid
14:03 : binary tree a binary search tree est
14:07 : for short in order for your binary tree
14:10 : to be
14:10 : valid binary search tree it has to
14:13 : satisfy the property which
14:16 : is that for every node in the tree this
14:19 : left child has to have a smaller value
14:23 : than the parent and the right child has
14:25 : to have a larger value than the parent
14:28 : and that that property has to be
14:32 : satisfied
14:32 : at all times while you're working with
14:35 : the tree
14:36 : and it's it's the job of your algorithms
14:40 : your algorithm that have to modify the
14:42 : tree have to make sure
14:44 : after every modification that property
14:46 : is satisfied
14:48 : so there's like a family of algorithms
14:51 : that
14:51 : work on this tree that has to maintain
14:54 : that
14:55 : now i put numbers here because usually
14:58 : that's how they're taught
15:00 : how you put number here but this doesn't
15:03 : have to be numbers this could be
15:05 : a string okay it could even be a user
15:08 : record
15:09 : that that goes inside the binary node
15:12 : all that matters
15:13 : is that there's some way to compare
15:16 : the values uh between
15:20 : two nodes and you can tell me
15:23 : given this versus this or this versus
15:26 : this or this versus this
15:28 : is one of them greater than the other or
15:30 : are they
15:31 : equal that's how that matters this is
15:34 : how an index is actually
15:38 : represented in a database
15:41 : and when you insert a new
15:45 : entry into this index such as
15:48 : emily let's pretend emily is 11.
15:52 : like i said these could be strings too
15:54 : so you could just insert
15:55 : a string emily but let's pretend emily
15:58 : is 11.
15:59 : so if you if you're inserting 11 into
16:02 : this
16:03 : binary tree you're gonna find where it
16:06 : needs to be and
16:08 : it goes and if yeah so you start from
16:11 : the root of the tree and then you're
16:13 : gonna
16:14 : go to if 11 is smaller than
16:18 : that note you're going to go left to get
16:20 : to
16:21 : 5 and then because 11 is greater than 5
16:23 : you're going to go right
16:25 : and then because 11 is greater than 7
16:27 : you're going to go right and
16:28 : stick stick 11 right in here well then
16:31 : you can do a login
16:33 : exactly this is a login insertion
16:36 : because
16:37 : you made as many hops as
16:40 : the height of the tree n is the number
16:43 : of nodes in the tree
16:45 : the height is going to be the log of
16:48 : n so you you have to traverse
16:52 : proportional to the height what about uh
16:54 : to find the node
16:55 : is it yes the final node is also log n
17:00 : if i wanted to find
17:01 : any number in this tree or even a
17:04 : non-existing number
17:06 : to figure out whether that it didn't
17:08 : exist there
17:09 : i do the same algorithm if the thing i'm
17:12 : looking for
17:13 : is smaller i go left the thing i'm
17:15 : looking for is greater i go right
17:17 : okay until i will get to the leave of
17:19 : the tree where i will either find it or
17:21 : find that it isn't there gotcha so
17:23 : that's also login
17:25 : so that's nice that's that's the
17:26 : beautiful things about
17:28 : trees in computer science uh the trees
17:30 : really is
17:31 : like my favorite data structure because
17:35 : the tree is a trick that allows
17:38 : all of the common crud things you do
17:41 : with data structures
17:43 : to be log in time what if
17:47 : this tree is always goes like one way
17:50 : like this what what if all the numbers
17:53 : go this
17:53 : side well what happened yes this is a
17:56 : common problem
17:57 : you're basically pointing out the
17:58 : problem that we can only
18:00 : enjoy this benefit if the tree is
18:04 : balanced because it's possible for a
18:08 : any trina to not have children the left
18:11 : of
18:11 : 10 is null and the left the right of 10
18:14 : is
18:15 : no so given that it's it's possible that
18:19 : we
18:19 : instead of getting something like that
18:24 : like if you insert one
18:31 : next you decide to insert three right
18:35 : and then you get four next and then the
18:37 : left of one
18:38 : is null and then you next you decide to
18:41 : insert four and he's like oh where is
18:43 : four of
18:44 : four greater than one so go right four
18:47 : is greater than three so go right
18:49 : and so forth and and and this
18:52 : this side is null and then you insert
18:55 : five
18:56 : and so forth so it just keeps on going
18:59 : only to one direction yeah and this is
19:02 : this is uh
19:03 : this is on the balance tree and we don't
19:05 : get to enjoy the benefit
19:07 : of getting log end time because we're
19:10 : not using
19:11 : the left side of any of the three nodes
19:13 : this
19:14 : is equivalent to a linked list so um
19:17 : so one thing about this is compute
19:19 : scientists have
19:20 : discovered that if you do this in order
19:24 : insertion like like if you insert the
19:27 : notes
19:28 : in the order of the values
19:31 : you will definitely have this problem oh
19:33 : yeah however
19:34 : if you insert these guys in a random
19:37 : order
19:38 : then usually you don't have a problem
19:40 : usually you have a pretty balanced tree
19:43 : kind of like this okay so there's one
19:45 : concept that
19:46 : tries to solve the problem using random
19:49 : number
19:49 : generation it's like at what what if
19:52 : these were
19:53 : inserted randomly um there's several
19:57 : ways there's there's several schemes and
19:59 : this is
20:00 : might still be an area of research of
20:03 : algorithms that
20:04 : makes sure the tree is balanced
20:10 : now one of those ideas is red black
20:12 : trees
20:13 : so red black trees is
20:16 : one of the famous ideas there's a whole
20:19 : chapter dedicated to
20:20 : red black tree i'm not gonna go into too
20:23 : much detail
20:24 : because it's kind of complicated but i'm
20:26 : just gonna explain the gist
20:28 : we're gonna color each of the notes of
20:31 : the tree
20:32 : either red or black
20:35 : in the book it's actually black gray
20:38 : trees
20:39 : because there's a black and white book
20:41 : but anyway similarly to
20:43 : how in the binary tree there's that
20:45 : property
20:47 : that always have to be maintained right
20:49 : for it to be valid
20:51 : a red black tree has a additional five
20:54 : properties
20:55 : that must be maintained in order
20:58 : for the tree to be a valid red black
21:00 : tree every note
21:01 : is either red or black okay that's easy
21:04 : the root must be black
21:06 : every null pointer is interpreted as
21:09 : black
21:11 : if a node is red then both as children
21:14 : must be black and for every note in the
21:18 : entire tree
21:19 : all paths starting from that note to the
21:22 : bottom leaf must
21:25 : contain the same number of black notes
21:28 : that
21:29 : like if i start from any note in the
21:31 : tree should i count myself or not
21:34 : okay anyway if i don't count myself it's
21:36 : one two three
21:37 : here one one two three here
21:40 : one two three here one two three here
21:43 : one
21:44 : two three here one two three here one
21:46 : two three here
21:47 : we must be complicated to keep it up
21:49 : yeah well wait
21:50 : well the people who invented this
21:52 : concept they
21:53 : gave you an algorithm as long as you
21:57 : implement the algorithm correctly
21:59 : there's an insert procedure if you
22:01 : follow that algorithm
22:03 : it'll guarantee that this is maintained
22:05 : okay
22:06 : um and to give you an idea of how that
22:09 : works
22:10 : so if you insert a new note which is z
22:13 : you're looking at your parent and it's
22:15 : like no my parent is red i cannot be red
22:18 : i must be black so it does a change to
22:22 : the tree
22:23 : so what it does is oh it just made
22:27 : both my parent and the sibling of my
22:29 : parents black
22:30 : to maintain this and then what what's
22:33 : more
22:34 : yeah exactly then the parents parent has
22:37 : to change color as well you keep moving
22:41 : the change up the tree okay so it could
22:45 : potentially propagate like more and more
22:47 : changes all the way up to the root so
22:49 : the result of
22:50 : adding this four here record
22:54 : uh three separate steps propagating and
22:57 : change
22:57 : up the tree in the second step it
22:59 : actually
23:00 : moves some of these nodes over to the
23:02 : left it's called a rotation
23:05 : and that's kind of how the tree
23:07 : automatically keeps itself balanced
23:09 : sometimes this is too heavy and you have
23:11 : to move some things over
23:13 : and then and then here it actually moves
23:16 : some of this stuff over to
23:18 : the right side so now it's actually you
23:20 : can see it's much more balanced
23:22 : because as the end result of this
23:24 : algorithm there's
23:25 : this this seven actually got moved up to
23:27 : the root
23:28 : the seven used to be here it got moved
23:31 : up to the root
23:32 : but would that be more than like log n
23:35 : because you spend log n to insert the
23:38 : four right here
23:38 : and then you do all these well this this
23:41 : propagation
23:42 : can at most propagate up as
23:45 : much as the height of this oh okay so
23:47 : that's two times
23:50 : or constant one times log n plus
23:53 : constant two times log so at the end you
23:56 : still get log n
23:57 : okay gosh so so this is yeah so even
24:01 : adding the cost of maintenance of the
24:03 : tree
24:04 : you still get login nice and that's
24:07 : that's i guess what we're after but but
24:09 : still uh there are other algorithms
24:11 : other schemes other than red black tree
24:13 : okay
24:14 : so anyway so so that's how this kind of
24:17 : the this tree maintenance
24:19 : stuff it's actually kind of hard
24:21 : computer science stuff
24:22 : but it's you know there's well-known
24:24 : literature about it and you can learn it
24:26 : um the person who events is very smart
24:29 : because yes they came up with solve the
24:32 : issue
24:33 : yeah so at the end of the day uh so
24:36 : if we can assume that we have algorithms
24:38 : that keep
24:39 : our tree balanced like this we can be
24:42 : guaranteed a login time for
24:44 : ins inserting into a tree which we're
24:47 : going to use
24:48 : for an index right so so we don't have
24:50 : to worry about
24:51 : the updating of the index being slow
24:56 : if we decide to index a lot of different
24:58 : columns
25:00 : updating a user or inserting
25:03 : a user or deleting a user will have to
25:06 : go in and update
25:07 : maybe one or more of the indexes and
25:10 : each one will take
25:11 : login time however that can still add up
25:15 : though okay
25:16 : even log in time if you you add up a lot
25:19 : of those
25:19 : can still be a lot right so that's why
25:23 : we don't tell people just index
25:25 : everything okay
25:28 : okay now now let's talk about like how
25:30 : do these
25:31 : indexes go on pages
25:34 : uh just there's the last thing we'll
25:37 : talk about
25:37 : databases use b trees which is
25:41 : like a binary tree except that every
25:44 : node can have
25:44 : more than one children okay like the fan
25:47 : out is much
25:48 : greater which it's also nice because
25:52 : any number if you find how
25:55 : the height of the tree in base 2 is a
25:58 : certain height
25:59 : if you if you use a larger base the
26:02 : height is going to be much
26:03 : smaller so which is nice
26:06 : to have a larger fan out what the
26:08 : database does
26:10 : is use an entire page as one of these
26:13 : nodes of the tree okay
26:16 : so a page let's say a page is 124
26:21 : bytes so i'm gonna store the key
26:25 : plus the uh plus each
26:28 : child of the tree which there can be
26:31 : more than two
26:32 : so first i'm gonna store my key and then
26:36 : these are pointers to other pages
26:42 : which are my children so
26:45 : and then each one of these are gonna be
26:48 : a page
26:49 : and because each one of these is only an
26:52 : address
26:53 : the fan out here could be really really
26:55 : large that this i have 124 bytes here i
26:58 : could store a lot of addresses here
27:00 : this could be 100 even a thousand
27:03 : pointers to other pages
27:05 : um so cut but conceptually it's
27:09 : exactly the same as a binary tree it's
27:11 : just the fan out it's much
27:13 : bigger okay and and from a operational
27:17 : standpoint you can think of it as well
27:20 : to in order to
27:21 : walk down one level of the tree has to
27:25 : get
27:25 : the next page which sometimes requires
27:28 : me to
27:28 : read a block of data from the disk
27:32 : if it's not already in memory so it's
27:34 : like each
27:35 : each time you walk down one step to the
27:38 : tree
27:39 : in the binary search case it's just you
27:42 : either go left or right but this case
27:44 : you can you can go yeah yeah so you
27:47 : compare
27:48 : the thing to 12. uh actually okay this
27:51 : is not accurate
27:53 : next to each of these pointers there's
27:55 : actually also a number
27:58 : so this might be down 24
28:01 : 26 27
28:04 : right each number is pointing to like if
28:08 : if it's
28:08 : less than this number then go to this
28:10 : page if it's
28:11 : if if the key you're searching for is
28:15 : in between these two numbers or
28:17 : something then go to this page
28:18 : if it's the next uh it this this is
28:21 : marking these ranges basically
28:25 : so it's within this range go to this
28:26 : page within this range go to this page
28:28 : within this range go to this page
28:30 : whereas this is just greater than outlet
28:32 : okay
28:34 : would like like a like a database like a
28:38 : no sql database does it work the same or
28:40 : it would be really different
28:41 : and no sql databases work the same way
28:44 : this is
28:45 : true of both yeah i guess it takes
28:48 : people time to to invent algorithms like
28:52 : this
28:52 : yeah they can write read and write
28:54 : really fast
28:55 : yeah there's many many years of
28:58 : innovation in computer science before
29:02 : yeah because before we have computer
29:04 : science just think about you have like
29:05 : library right if you have a library then
29:07 : you have
29:08 : a lot of books that you have to uh make
29:11 : a system so that
29:12 : you can quickly find a book your
29:14 : libraries came up with
29:15 : their their own system and that that
29:17 : there was a lot of years going into it
29:19 : right figuring that out also well i
29:22 : think it's a similar system
29:24 : yeah it's like they they have like a
29:27 : letter
29:27 : that's based on the category of the book
29:30 : and then there's the next letter it's
29:33 : based on the subcategory of the book and
29:34 : then there's the next letter
29:36 : yeah so it's similar to this this idea
29:39 : yeah
29:40 : yeah the the binary tree and the b tree
29:43 : is
29:44 : they're not using a predefined number to
29:47 : figure out
29:48 : how to go to the next level they just
29:50 : figure that out dynamically based on the
29:52 : data that's coming in
29:53 : yeah cool thanks this is nice you're
29:56 : welcome