Databases: How Would You Implement...?

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.