What data structure is this?

Question

Imagine I have a set of houses I want to sell and I want to present then on a website. The user should be able to filter the house they want by price, city, number of floors, area etc. However, I don't want it to be like this:

First select price only, then you can select city and only after that can you select the number of floors etc.

I want the user to be able to pick the order of attributes he wants.

For each iteration (attribute selection) the set of remaining attributes will have a limited range depending on the previous interaction and so on.

I have seen this implemented on some sale sites but I don't know how this is implemented, specifically with regards to the the data structure.

It doesn't look easy to add new houses for example. It feels like there is a complicated combination of binary trees and linked lists but there is probably a far better way that I haven't figured out.

• Arseni Mourzenko: Not sure I understand your question. The problem you describe is ordinary filtering. No matter if filters are specified sequentially or in any random order, they will translate into a single clause with multiple conditions, would it be in a form of a SQL query or any other form.
• Robert Harvey: It could be as simple as a WHERE clause, applied to each of the attributes' queries. For example, let's say you have "Price" and "Number of Garages" as attributes. If your user selects houses under 200,000,ドル your WHERE clause will be price < 200000. It's entirely possible that, when you apply this clause to Number of Garages, the range for number of garages will shrink to 1 or less.
• Mandrill: Exactly Robert, but I was considering implementing this in C for example, not a scripting language, so do I really need a database package to do this? Is it is really complicated, non trivial task to do with basic structures (linked list, binary trees and some loops)?
• Robert Harvey: Yes, you need a database to do this. Every web site on the planet having similar filtering uses some queryable data store to accomplish it. Nobody reinvents this particular wheel. Sure, you can do it with lists or trees, but you'll be re-implementing what databases already do very well.
• Erik Eidt: You're going to be storing your listings in a database anyway, so just ask it for the filtered results you need. (If you aren't using a database, then you're going to invent persistence AND filtering (from scratch).)

Answer 1

This is easily implemented in SQL. Even better is the realization that any reasonable DBMS will give you the option to store the data as a btree+ or a hash table. You also have the option to put multiple indexes on the table structure. You don't have to configure this.

You project reminded me of a project I did about 20 years ago. For fast access, I was told to implement a tree like structure, perform some calculations on the data and then produce a report, all done in C - we didn't want the overhead of a DBMS.

Due to the complexity of the tree like structure and ever changing sample data, it took about 6 months to work out the data collection and storage in the tree. We then dicovered that we were attempting the knapsack problem. We gave up on that project after that.

This experience informs my decisions to this day. Looking back with hindsight, I could get to the same place with a trivial database structure and maybe a couple of weeks of programming.

In summary: use C for what it is good for, and use SQL for what it is good for. First do the database solution with a combination of C and SQL. Only consider replacing the DB with C structures when it proves to be too slow.

• Neil: My experience has taught me that when you get to the heart of it, data management is exactly what a database does best, and it does it well. Therefore if you can do it through the database without compromising flexibility, you do it, no questions asked.
• user251748: "I want a round thing with a hole in the center, that rolls along the ground carrying things for me, but I don't want the overhead of a wheel." The knapsack problem then becomes: how can I pack up my knapsack and leave fast enough?
• Robert Baron: No comprrnde, you certainly deserve a award for that. It made my night.