Stejně jako většina firem v našem průmyslu i my jsme založili náš byznys na otevřeném softwaru. Jsme trpaslíci, kteří stojí na ramenech obrů – nanos gigantum humeris insidentes. Celé roky využíváme software vývojářů, kteří nás svými znalostmi převyšují a kteří svoji práci poskytli zdarma ku prospěchu všech.
Mnohokrát jsme si pokládali otázku, jak tento dar oplatit. Jednou z možností bylo přispívat do některých z OSS nadací, ale usoudili jsme, že peníze lépe pomohou jinde.
Our e-commerce view engine (E.V.E.) works with matrices of sorted number on the lowest level of its application logic. I’d like to describe some of the algorithms we use to combine such matrices in logic operations.
Why do we keep data in matrices in sorted order? There is a price to be paid when adding new number to the matrix when sorted order is required - appending number on last position would be much faster.
I’d like to start series of posts about problems we’re facing in e-commerce area and what algorithms we used to solve them. There are a lot of e-commerce sites on different levels of complexity in terms of feature richness, data amount, throughput requirements, consistency and realtime updates. Let me first introduce the situation we’re trying to handle and then move to the solution space.
Domain Let’s look at example of some e-commerce site product listing:
MPTT it quite old and very clever way for transposing hierarchical - tree structure to a two-dimensional representation that is suitable for relational databases. MPTT allows to translate information about node tree position into two numbers - left and right bound. Two number fields can be easily indexed and look ups for records in the tree can take advantage of database indexes and perform really quickly.
I won’t go into details of the (well) documented MPTT algorithm itself, because there are a lot of sources where you can go for comprehensible explanation (better than I would be able to provide).
