21. Database Indexing: How DBMS Indexing done to improve search query performance? Explained

➡️ Notes link: Shared in the Member Community Post (If you are Member of this channel, then pls check the Member community post, i have shared the Notes link there)
➡️ Join this channel to get access to member only perks:
/ @conceptandcoding
Discussed various points in detail:
- How DBMS stored the data in DB
- How B tree is used for indexing
- What is clustered and Non-clustered Indexing
- How it able to search data faster.
support this channel:
/ @conceptandcoding
#softwareengineer #database #dbms

[@ConceptandCoding]

Don't miss this: HLD Basics to Advanced: kzbin.info/aero/PL6W8uoQQ2c63W58rpNFDwdrBnq5G3EfT7 LLD Basics to Advanced: kzbin.info/aero/PL6W8uoQQ2c61X_9e6Net0WdYZidm7zooW JAVA Basics to Advanced: kzbin.info/aero/PL6W8uoQQ2c63f469AyV78np0rbxRFppkx

[@drpstar]

Postgresql use heap tables and doesn't have concepts like clustered index. What is your thoughts on that? How indexing works there and what are the pros and cons of these approaches? I asked a lot of questions😅, please reply if possible. Thanks for the detailed explanation.

[@revvedupofficial]

no one, i repeat no one, explained like this, thank you so much for uploading these types of indepth videos 🤩

[@ConceptandCoding]

thats a lot buddy 🙏

[@atmurisaimouli4697]

We want more videos like this and creators like you ✌️

[@NeverGiveUp186]

Amazing explanation Shrayansh. Absolutely loved it !! If my college professors took even 10% of the efforts taken in this video for explaining the topic, life would have been so much better xD

[@ConceptandCoding]

Thanks 🙏

[@shawkiahmed3586]

I would say, this is one of the most amazing explanation i have ever seen on indexing. Previously i only knew that indexing can make search faster but now i understand all the internals about indexing. Thanks so much for your effort. Take love from Bangladesh.

[@Shivam-wk6sq]

Piece of gem. One of the best videos on indepth indexes.. Thanks for the this video Shreyansh

[@vkhemant]

One of the best videos I ever saw on indexing. Thanks Shrayansh.👌

[@anjaligupta5044]

You are such a good teacher. Everything was so clear. Thanks a lot Shreyansh. :)

[@socialmedia5173]

Dude hats off , who put this effort Your channel is most underrated Keep creating ♥️

[@srawat1212]

+1

[@Gengar_33]

Fun fact: Actually B in B tree is not an acronym for anything. Rudolf Bayer and Edward M. McCreight in 1972 came up with the idea of B tree. "B" was later given a meaning by people, most widely used one being "balanced" Btw Amazing explanation!! Learnt new things and refreshed my concepts

[@sravyaparsi7952]

You have explained the concepts crystal clear. Thank you Shreyansh.

[@ConceptandCoding]

thanks

[@tanazshaik678]

I am glad I found your channel Sir! Respect...

[@rishabhagarwal8049]

Thanks Shrayansh, I got the Indexing in one go

[@anusuyaganguly6009]

In depth explanation in a smooth readable format.

[@ConceptandCoding]

Thanks

[@sameer_sah]

Thanks a lot Shreyansh ! Very informative. Watched till the end. Recalled a lot of forgotten concepts 😄 (data blocks, database pages, B/B+ trees, cluster/ un-clusted indexes ) Bookmarking this. Please add 'video chapters' if possible.

[@ConceptandCoding]

Thanks

[@Rajag-ic1xt]

you are amazing man, It is so clear to understand

[@randheer.chauhan.2]

Great explanation Shreyansh 👍 For the first time i got to know how indexing really works internally.

[@ConceptandCoding]

thanks buddy

[@user-pv4ft1qq2l]

Finally I can say now I know what is indexing.. Thanks for this video

[@ConceptandCoding]

Welcome

[@AtharvaRao0104]

Great video! I like it because you have questions before explaining the concept .. that makes us think a bit than just listen passively .. perhaps after the question you can ask the viewer to pause and think .. eg: pause and think how you can make the search faster than O(N) .. just an opinion

[@ConceptandCoding]

Thanks for the feedback buddy

[@user-fl1zk7bz1g]

Hi Shrayansh, first of all, a big thank you for providing such valuable content. it deepens my curiosity about the internal workings of indexes and B+. I have a small request: could you please host a live session where we can discuss our understanding of the video and implement an index on a table. Thank you

[@ConceptandCoding]

Sure buddy, i will plan for it.

[@deepakrana2388]

Thanks Shreyansh!! Content is pure Gold 🎉

[@ConceptandCoding]

Thank you

[@vishalghanghav748]

Shreyansh , Can you please post videos around weekend or keep public upto the weekend whenever posted

[@ConceptandCoding]

Noted, it make sense Vishal.

[@meyankgarg2686]

boss kamal ka explaination hai

[@zishanshaikh9375]

Thank you for making this video, very clear & detailed explanation, could you please make a video explaining how composite index containing multiple columns will work ? how the BTree will be created and used for searching

[@anveshkonda8334]

Thanks a lot @Shreyansh

[@rakeshverma6867]

Excellent explanation.

[@laymancode4433]

Just love this type of content . God bless you 💕💕❤

[@ConceptandCoding]

Thanks

[@pranjalsharma7650]

Really admire your content man!!

[@ConceptandCoding]

thanks

[@chgeetanjali7919]

Very informative .. thanks for the video... i had a clear understanding of indexes now

[@ConceptandCoding]

thanks

[@KishoreThatavarthi]

Thank you Shreyansh for amazing content

[@ConceptandCoding]

Thanks

[@nawaahkh]

Thank you a lot for this great content with amazing explanation. 👍

[@ConceptandCoding]

Thanks

[@DurgaShiva7574]

Lots of doubts in this video.. please make a live session 🙏

[@srawat1212]

Quick question: How does a new column insertion affects the clustered index ? Now since the size of each row has changed...the number of rows that can be accommodated in a page should be less than what it was before. Can you please explain it as well ?

[@brajkishore32]

Adding new column will not affect clustered index. It will affect Data Page/record only

[@arshkatyal2807]

Amazing explanation shrayansh. Just 1 question here(for anyone 1 Basic difference we got b/w clustered and non clustered index is that, in clustering, offset maintains the order in data pages in which B+ tree has sorted But what advantage does that offset sorting gave which is not present in non clustered indexes. Please let me know if anything is unclear.

[@mahboobhasan2137]

nice video, very informative.

[@vaaidooyt1837]

Shreyansh when you told that you are making it public for only 2 days at that time i downloaded the video as it was long and i want to understand with peace and slow pace as I'm a working professional. Honestly loved the video ❤

[@ConceptandCoding]

thanks a lot. actually got many msgs to keep it till weekend as during weekend only they will get time to watch. So till weekend i will keep. Take your time to understand and watch buddy

[@vaaidooyt1837]

@@ConceptandCoding ❤️❤️❤️❤️ thanks for your precious time

[@bijanzohouri98]

Very good explanations on indexing

[@ConceptandCoding]

Thanks

[@vinaysharma7072]

best video database index

[@manoharmanu9240]

Great Explanation 👏👏

[@anasyousaf4439]

Great

[@SadikSadhi-se7pp]

Great video Shrayansh! Could you please explain about the composite index working as well?

[@IsolatedMonk]

Thanks Shrayansh for this amazing explanation, qq: who does the conversion from a data page to a data block?

[@sukritiguin5637]

You gave more than your 100%. ❤❤

[@ConceptandCoding]

thanks

[@akashdutta1620]

Data Pages - This is what dbms creates, usually of size 8kb Data page - Header(Page No, Freespace, check sum), Data Records, Offset Array.. For one table, dbms can create multiple data pages. Data pages actually stored in data block in physical memory Dbms have no control in data block, so it maintains a 1:1 mapping of Data Page to Data Block Indexing - It is a technique used to query the database faster. B+ tree is used to implement indexing, it provide O(log n) for searching, insertion, deletion. B+ tree It maintain sorted data All leaf node are at same level M order Tree means, each node can have atmost M children and M-1 key.

[@ConceptandCoding]

👍

[@akashdutta1620]

@@ConceptandCoding Please ignore I am just taking notes

[@mahanteshambali]

I really liked the video. Thank you for your work. Could you please point to resources you used for this video. Like Books or Blogs it would be helpful.

[@ConceptandCoding]

Thanks,to be honest, most of my learning is through working and by giving interviews.

[@mahanteshambali]

@@ConceptandCoding thank you

[@kushalunune2084]

Thanks for the incredible content. Iit wouls also be helpful if you provide a short segment of links/books/articles you used while studying these topics.

[@arpit3640]

Very good explanation Shreyansh 👍

[@ConceptandCoding]

thanks

[@2412_Sujoy_Das]

This was probably gonna be the 5 star video according to me, but after 1:10:00 mins, you hastily explained everything shreyansh which is the last thing any beginner would want.... Anyways nice explanation 👍

[@ConceptandCoding]

Thanks for the feedback, non clustered index and index Pages right, i will explain in separate video buddy, thanks for the feedback

[@najimali32]

Amazing video Shreyansh 🎉

[@ConceptandCoding]

Thanks

[@arishtajain8372]

You missed one crucial point while explaining page splitting. The actual data records within the data pages themselves do not rearrange or move during the split operation, unless it is happening on the clustered index, because in the case of clustered index the DBMS needs to store the data records in the sorted order of the index, otherwise why would it care about the order in which the data records are stored if the B+ tree is on a non clustered index.

[@buntykumar7270]

Nice notes

[@Siddik-ko8ol]

Thanks a lot!!

[@sahilgarg3460]

Good one, thinking to find same topic with some good explanation found it here.

[@ConceptandCoding]

Thanks

[@MDJahidHasan-de8bk]

brother it is a great lecture and It is very much understable. But I have a doubt about the data page section. In which time the data page is created, -- when the B+ tree (indexing) is created or when user first time create data. Or different data page is created during the B+ tree formation, or during creating index(B+ tree) the old data page is updated? I am not clear about this part. I am waiting for your reply and again your lecture is awsome.

[@syamreddy-oq7cz]

Hi Shrayansh, Explanation is really amazing, One query : Why the page split happens? What is the need of it.

[@ConceptandCoding]

Page splits occur in databases to maintain the structure and efficiency of indexes. When an index page becomes full and a new entry needs to be inserted, the page is split into two to accommodate the new data. This ensures that the index remains balanced and efficient for fast data retrieval.

[@bikeshregmi2392]

nice

[@drpstar]

Postgresql use heap tables and doesn't have concepts like clustered index. What is your thoughts on that? How indexing works there and what are the pros and cons of these approaches? I asked a lot of questions😅, please reply if possible. Thanks for the detailed explanation.

[@godbhaigod]

Even he dont know😂😂

[@SuperLucasGuns]

nice. subscribed.

[@lokendrasingh5805]

Great explanation. Love it. Can you please explain how the compound index(name, address)is stored in the b+ tree? also, just one small favor by mentioning which drawing software is used here.

[@lokendrasingh5805]

@Conceptandcoding Please confirm

[@boerliu3668]

you are awesome!

[@PradeepSingh-ov3bt]

Just a quick question , if i have multiple non-clustered column indexes in a table I am writing a query which includes these columns in where condition , now dbms will use which index here ? In below example merchant_id, date_created and order_id all three are non-clustered indexes select * from order where source_id = 'xyz' and merchant_id ='xyz' and date_created >= (NOW() - INTERVAL 30 MINUTE) and order_id like "pf_%"

[@tejasshaha6629]

Very very good video. Just 1 question - How costly it is for DBMS if we are inserting 1 row and it is resulting into multiple page splits ?

[@aayush7099]

Amazing video

[@ConceptandCoding]

Thanks

[@amanvikram04]

Hi shreyansh, thanks for very detailed explanation on database indexing , i just want to know do you have any video on sharding or not , if yes then please help to redirect if not then request you to make a video on it please ,Thank you so much

[@ConceptandCoding]

its not there yet, i will make

[@amanvikram04]

@@ConceptandCoding thank you so much

[@arunpandya401]

Hi Shreyansh, thank you for the detailed explanation. I have one doubt: If we are creating clustered and non-clustered indexes, how will it perform page split? As per my understanding, it will always try to put the nearest B+ Tree node values in one data page. Now it is certain that for clustered and non-clustered index B+ Trees values there is a conflict in storing rows in data pages.

[@ConceptandCoding]

Okay consider this, Data page is mostly pointed by Clustered index nodes Non clustered index points to clustered index and from their it goes to data page. 2 hop it has to do. But in some DB, non clustered index also points to data page. But I did not understand when you say conflict? Insertion always happens based on clustered index.

[@sumitroy7817]

hey, nice explanation. thank you so much. can you please explain ACID and normalisation too.

[@ConceptandCoding]

sure

[@balakrushnabehera2800]

Hi Shreyansh amazing video i watched to the end but i think more insights on index table is needed because when it is around 1:19:34 you mentioned about index table prior to that there is no mentioning of index tables/pages. And i felt like when we execute a search query how the procedure follows from beginning needs to be explained starting from index pages.

[@ConceptandCoding]

I have explained in end the sequence when query comes. Sure I will explain Index pages more through short videos

[@balakrushnabehera2800]

@@ConceptandCodingthanks 👍

[@adityaallam]

Great Explanation sir! why cannot hashmap be used instead of B + trees for indexing?

[@ConceptandCoding]

HashMaps are not suitable for indexing in all scenarios because they lack the ability to efficiently support range queries and ordered traversal, which are essential features provided by B+ trees. B+ trees maintain sorted order of keys, making them ideal for range queries and efficient traversal, whereas HashMaps do not guarantee any specific order of keys.

[@adityaallam]

@@ConceptandCoding Thank you :)

[@ayushiagarwal2306]

Thanks for a great video. I had one query : At what time is offset stored in data pages in case of clustered index? Is it when a data page is full or is it at insertion of each row? How is the order maintained in offset?

[@ConceptandCoding]

With every row insertion, offset is also updated. And order is maintained according to order of clustered index.

[@PawanKumar-cw9ko]

Hi Shreyansh, What is an index page? Is it the same as a data page or something else?

[@ConceptandCoding]

mostly same as Data pages, but stores indexing related information

[@RJ-nt3ol]

@Shreyansh, If we have not added indexing first, then data pages will be stored. Now if we add indexing, then all those data pages will again be refactored as per the indexing. Am I right?

[@ConceptandCoding]

Yes

[@MDSAJID-vh6ho]

@Conceptandcoding where this index itself store? How DBMS know the location where index is stored?

[@ConceptandCoding]

it creates index pages

[@clutchh_god]

does page splitting happens for non-clustered index also?

[@Aakashkumar-re7gk]

great video one doubt b/w clustered and non clustered clustered means create index on a primary key non clustered means create index on other keys the example in the video where we create a clustered index on empId which is ok but when we create non clustered index on employee name I have a doubt Problem because you said when there is an entry in b+ tree to choose a paricualry data page it sees to its neigbour data page if empty insert otherwise split it Doubt is now we have two b+ trees one based on Id and other on name if first binary tree say row will go to data page 1 and other b+ tree says row will go to page 2 in which page we will make an entry?

[@kolasphoorti1030]

Hi Shreyansh, really a good video, helped in understanding index in depth. I have 2 questions: 1. I did not really understand how page splitting is happening here. Is it based on the order of index? (ascending order). if yes, is it really needed? We can just put it in next free page and maintain pointers to the data pages. 2. In non-clustered indexing, I don't understand how the data is accessed in O(logN). The accessing of data page from B+ tree as I understand is O(logN), but there is no pointer to the row inside data records of the data page, as a result it should scan whole data page as In understand? In clustered indexing though, since the order of index is maintained in offset, we can use a binary search to get to the correct row given the index value. I was always assuming along with the data page mapping in B+ tree, there should be some kind of map which has key as index value(column value) and value as pointer within data page.

[@ConceptandCoding]

Page splitting again is a very interesting topic to understand. Since you asked, i will try to explain why page split is done instead of just create a new page. Actually when DBMS first select the most appropriate Data Page for the new item to put and there is no space, it will create new data page and let say adds the new item in the newly created data page, but it also does one more thing, that in 1st data page it also adds the address of newly created data page (so it has to split some item which is present in 1st page to new data page). That's why when we say, during page split it divides the rows bcoz DBMS stores pointer of newly data page in existing data page, so it need some space. Second regarding Non-Clustered Indexing, in most of the DBs it first point to Clustered index and then fetch the data page, so it's kind of 2 hop. (And regarding O(logn) search, it can find the correct data page in O(logn) and searching the row inside a data page is just constant time as data page size is fixed)

[@kolasphoorti1030]

@@ConceptandCoding got it. Thank you

[@anishtaneja5665]

Shreyansh , video is amazing . Only point regarding non clustered index , it’s not clear how it is referencing page / row for retrieval ?

[@ConceptandCoding]

There are 2 flavours of Non clustered index: - it points to clustered index and from there it goes to data page(2hop) - it also directly pointing to data page. Depends upon DB to DB. They Store the reference where to look up for the data.

[@anishtaneja5665]

@@ConceptandCoding . Thnx !!

[@ancyzachariah5491]

How to get notes of this indexing topic

[@aayushsingh3140]

why use b+ tress instead of hashmap

[@gurnoorsingh2954]

Does clustered index also uses B+ tree? Because it can use the offset concept in a single data page. But apart from that I believe it needs to use B+ tree. Can someone confirm?

[@DevanshChiluka]

❤

[@harshitagarwal2682]

👍👍

[@sunilpatel6542]

Hey buddy just want to know in composit index I have table that have index on (a,b) column - If I do where condition only on a column will dbms use (a,b) index - And how B-tree store composit index

[@ConceptandCoding]

For composite index it will create B+ tree just by concatenation both a,b column values. So in where clause, it would be able to use B+ tree when in search query where clause if you provide either: a (able to search in B tree) a and b ( able to search in b tree) b (won't be able to search in B tree, bcoz while creating B tree it first uses a)

[@karmicveda9648]

🔥🔥🔥

[@ConceptandCoding]

Thanks:)

[@aadityaupadhyay6264]

Nice tutorial, I have one doubt How is the order defined of B+ tree in the DB? Here you have taken 3, in real case scenario on what basis it will decide?

[@ConceptandCoding]

This Changes from DB to DB buddy. Depends on many factors one such factors is size of Data Page and size of data blocks. Based on such factors it compute and decides what Order B tree it has to create.

[@aadityaupadhyay6264]

@@ConceptandCoding thanks for clarifying.

[@mcspraint4591]

Can you please give me a first time offer on LLD HLD members only resources? I immediately need it.

[@clutchh_god]

what is the advantage of clustered index over non-clustered. Since in the both the cases, index will be pointing to the row's data page. Basically my doubt is, what is the added advantage of having offsets in same order as that of index, since index won't be aware of offset array index it needs to refer to for accessing the row

[@ConceptandCoding]

For Non clustered index, there are 2 flavours available depends upon DB to DB. - 1st which i mentioned, you can have many non clustered index key + clustered key also point to data page. - 2nd flavour is, we can have many non clustered key, but Non clustered key point to Clustered key index first and using clustered index they find the data page. So it's 2 hop. But we are always sure with clustered index is we can get the respective data page in one hop. Nice question btw.

[@clutchh_god]

@@ConceptandCoding got it.. but what is the advantage of having offset array in same sequence as of clustered index?

[@ConceptandCoding]

@@clutchh_godone of the advantages it gives during range search query.

[@sanchayyadav5308]

Shrayansh I think Physical memory is RAM not a disk(ROM)🧐

[@kratikharchandani7418]

Hi, this video was good but i didn't get what is non clustered index?

[@kratikharchandani7418]

also clustered index is primary key only so that we can sort the data according to it and store it and if no primary key is there then it creates an internal index which uniquely identifies a row, is my understanding coorect?

[@ConceptandCoding]

Right

[@ConceptandCoding]

Non clustered index is used for indexing on Secondary key or composite key. Rows or data pages are not ordered based on this index. And many times based upon DB, you will find that instead of directly pointing to data page it first point to Clustered index and through clustered index it goes to data page, so kind of 2 hop

[@kratikharchandani7418]

@@ConceptandCoding Thanks for clearing the doubt

[@devpratapsingh7050]

Can we have a common place for all notes link wrt to playlist

[@ConceptandCoding]

i did, pls check member community post section, you will get all notes playlist wise.

[@priyankam1271]

Hey, I am not getting Join for you channel to access exclusive content. Please help.

[@ConceptandCoding]

kzbin.info/door/DJ2HAZ_hW-DMJj_U0zN38wjoin

[@girishanker3796]

⭐⭐⭐⭐⭐

[@billion_dreams__7787]

Bhaiya payment Ka option hi nahi aa raha hai java vala, kuch process batao kaise payment karna hai

[@pos1421]

can you share the pdf of video ? for future revision

[@ConceptandCoding]

Pls check the description section buddy

[@Mohd_Rashid_Siddiqui]

Can you please share the notes link?

[@ConceptandCoding]

Yes I will put in description section by eod

[@subbunittala2012]

Hi

[@raghunathhembram9962]

bakwash faltu

[@021gauravverma5]

Bro if you have speak English so please speak clearly

[@ConceptandCoding]

Sure. Pls suggest some points where I can improve.

[@logicalrisi]

Notes achhe nhi hai