Databases: How Would You Implement...?
Buy or Subscribe
You can access this course in just a minute, and support my efforts to rid the world of crappy online courses!
Youâre sitting at your kitchen table at home and the house is quiet and hopefully remains so. You have a glass of water next to you and youâre looking forward to the initial interview, even if youâre a bit nervous. You make sure youâre not backlit by sitting in front of a bright window and you check your audio/video settings for the third time - you donât want to waste time with âcan you hear me???â
The clock ticks 1pm and you click the link for the Zoom meeting and see a person is waiting for you there. Her name is Samantha and sheâs the head of the data team at Company X.
Good morning, how are you today! Thank you so much for taking the time to talk with us. Before I go on - are there any questions you have for me?
You know itâs good form to ask at least a few questions and you do, inquiring about the job and maybe a bit more about Samanthaâs duties. Eight minutes go by and she moves the conversation back toward you.
I looked over your resume and I can see youâve done a lot of work with databases. Tell me aboutâŚ
She asks you a few light questions about a job you had as the âdeveloper DBAâ at your last startup using MongoDB and, more recently, about some light analytics work you did using PostgreSQL. She pauses⌠here it comesâŚ
The Question
The smile fades a bit and her face becomes a bit more serious - a queue for you so you know a technical question is about to be askedâŚ
If I was to ask you to implement an indexing engine for a database we were developing, how do you think you would implement it? Just a simple one at firstâŚ
You take a second and think about the question. You remember that itâs a good idea to make sure you understand whatâs being asked, so you begin to form some questions in your mind:
- I assume this is a fictional product and that it has no indexing just yet? Yes, thatâs correct.
- Will the index be used to for string queries or more structured data? String data.
- Iâm also going to assume this index will be used for rudimentary query optimization at a smaller scale - say up to a few million rows. Can I also assume concurrency wonât be a consideration just yet? Yes those assumptions are fine
Your Answer
OK, before you read on, consider how you might answer this. Take a second and put down your phone/ipad/laptop (or just look away from the monitor) and practice answering this. Itâs entirely likely you might not know anything about database indexes which is just fine⌠but then again you actually might know some basics about how they work. Itâs all data structures and algorithms after all! If youâre totally in the dark on this thatâs OK, read on just for fun to see how you might answer something more relevant to you.
The Simple Version
Most databases have some form of indexing that allows for faster searching and querying. Some databases, like PostgreSQL, allow you to choose what type of index you want to use - such as HASH, BTREE, GIN or GIST (among others). Each of these stores data in a particular way. Other databases have only a single type but they all do the same thing under the hood: pre-load some data into a data structure which is optimized for a search algorithm later on.
The simplest example which would answer the question above is to store the data pre-sorted so you could use something like binary search later on. For instance, you might want to index a users
table on their email address. The index would sort all of the user records based on email in the background and you could then query that index using binary search.
The More Complete Version
An answer that shows that you know your data structures and algorithms (which I hope you do by now!) would be to use something like a balanced binary tree to store the data with depth-first search for the query. Do you have other ideas on this? Great! However⌠Samantha wants to know how much you know databases. It might be tempting to go on about index theory but resist the urge⌠no one wants to work with a showoff!
Summary
The goal with this scenario is not to prove how much you know about databases, but to see how an intimidating question such as âcan you build an indexing engineâ can be broken down to an acceptable answer if you:
- Make sure to ask questions
- Calm yourself if you feel out of your depth
- Remember your data structures and algorithms - the answer might be right there!
And finally - if you really know an answer, show it by being as concise as you can.