*Bài viết được post tại https://phatng.com/luu-tru-du-lieu-voi-materialized-path/ *
Gần đây mình có làm 1 task khá thú vị về lưu trữ dữ liệu với SQL, tưởng chừng như kiến thức học SQL cơ bản ở trường đã giải quyết được tốt nhưng không! Trong bài này chúng ta sẽ cùng khám phá cách mà Cấu trúc dữ liệu (CTDL) và Cơ sở dữ liệu (CSDL) kết hợp với nhau để giải quyết bài toán thú vị sau đây cùng mình nhé.
Bài toán
Bài toán cần giải quyết như sau: giả sử cần lưu trữ các danh mục (categories) của 1 bài viết trên blog của mình, có các danh mục sau
Từ sơ đồ có thể thấy đây là 1 cây danh mục, ta có lập trình căn bản là cha của lập trình web và lập trình mobile và tương tự với những danh mục còn lại. Tiếp theo chúng ta sẽ nhúng tay vào SQL để tạo bảng lưu trữ các thông tin này xem sao.
Cơ sở dữ liệu
Mình chọn MySQL để lưu trữ dữ liệu, đây là cấu trúc bảng ban đầu mình nghĩ đến
1 2 3 4 5 6 7 8 | <span class="token keyword">CREATE</span> <span class="token keyword">TABLE</span> <span class="token keyword">IF</span> <span class="token operator">NOT</span> <span class="token keyword">EXISTS</span> <span class="token punctuation">`</span>categories<span class="token punctuation">`</span> <span class="token punctuation">(</span> <span class="token punctuation">`</span>id<span class="token punctuation">`</span> <span class="token keyword">int</span><span class="token punctuation">(</span><span class="token number">6</span><span class="token punctuation">)</span> <span class="token keyword">unsigned</span> <span class="token keyword">AUTO_INCREMENT</span> <span class="token operator">NOT</span> <span class="token boolean">NULL</span><span class="token punctuation">,</span> <span class="token punctuation">`</span><span class="token keyword">value</span><span class="token punctuation">`</span> <span class="token keyword">varchar</span><span class="token punctuation">(</span><span class="token number">255</span><span class="token punctuation">)</span> <span class="token operator">NOT</span> <span class="token boolean">NULL</span><span class="token punctuation">,</span> <span class="token punctuation">`</span>parent_id<span class="token punctuation">`</span> <span class="token keyword">int</span><span class="token punctuation">(</span><span class="token number">6</span><span class="token punctuation">)</span> <span class="token keyword">unsigned</span> <span class="token boolean">NULL</span><span class="token punctuation">,</span> <span class="token keyword">PRIMARY</span> <span class="token keyword">KEY</span> <span class="token punctuation">(</span><span class="token punctuation">`</span>id<span class="token punctuation">`</span><span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token keyword">FOREIGN</span> <span class="token keyword">KEY</span> <span class="token punctuation">(</span><span class="token punctuation">`</span>parent_id<span class="token punctuation">`</span><span class="token punctuation">)</span> <span class="token keyword">REFERENCES</span> categories<span class="token punctuation">(</span><span class="token punctuation">`</span>id<span class="token punctuation">`</span><span class="token punctuation">)</span> <span class="token keyword">ON</span> <span class="token keyword">DELETE</span> <span class="token keyword">CASCADE</span> <span class="token punctuation">)</span> <span class="token keyword">DEFAULT</span> <span class="token keyword">CHARSET</span><span class="token operator">=</span>utf8<span class="token punctuation">;</span> |
Và sau khi insert xong data như ở hình trên, ta được như sau
1 2 3 4 5 6 7 8 9 10 | <span class="token operator">></span> <span class="token keyword">SELECT</span> <span class="token operator">*</span> <span class="token keyword">FROM</span> categories <span class="token keyword">where</span> <span class="token punctuation">`</span>parent_id<span class="token punctuation">`</span> <span class="token operator">=</span> <span class="token number">3</span> <span class="token comment">-----------------------------------------------</span> <span class="token operator">|</span> id <span class="token operator">|</span> <span class="token keyword">value</span> <span class="token operator">|</span> parent_id <span class="token operator">|</span> <span class="token comment">-----------------------------------------------</span> <span class="token operator">|</span> <span class="token number">6</span> <span class="token operator">|</span> Progresstive web app <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">7</span> <span class="token operator">|</span> Hybrid app <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">8</span> <span class="token operator">|</span> Native app <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> <span class="token comment">-----------------------------------------------</span> |
Mình dùng khóa ngoại parent_id thực chất là reference đến chính bảng đó để lưu thông tin danh mục cha, điều này sẽ hữu dụng khi ta muốn truy xuất toàn bộ danh mục con từ 1 danh mục cha, câu lệnh SQL bên dưới để lấy tất cả danh mục con của Lập trình mobile
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | <span class="token operator">></span> <span class="token keyword">SELECT</span> <span class="token operator">*</span> <span class="token keyword">FROM</span> <span class="token punctuation">`</span>categories<span class="token punctuation">`</span> <span class="token comment">-----------------------------------------------</span> <span class="token operator">|</span> id <span class="token operator">|</span> <span class="token keyword">value</span> <span class="token operator">|</span> parent_id <span class="token operator">|</span> <span class="token comment">-----------------------------------------------</span> <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> Lập trình căn bản <span class="token operator">|</span> <span class="token boolean">NULL</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">2</span> <span class="token operator">|</span> Lập trình web <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> Lập trình mobile <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">4</span> <span class="token operator">|</span> Backend <span class="token operator">|</span> <span class="token number">2</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">5</span> <span class="token operator">|</span> Frontend <span class="token operator">|</span> <span class="token number">2</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">6</span> <span class="token operator">|</span> Progresstive web app <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">7</span> <span class="token operator">|</span> Hybrid app <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">8</span> <span class="token operator">|</span> Native app <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> <span class="token comment">-----------------------------------------------</span> |
Worked! Trông ổn thế cơ mà, cứ tưởng thế là đã xong task nhưng đời không như mơ anh lead vừa ngó vào xem code đã phát hiện ngay 1 trường hợp mà mình không nhìn đến:
Nếu muốn lấy tất cả danh mục con của Lập trình căn bản thì phải làm như thế nào? Theo cấu trúc này thì anh nghĩ câu query sẽ không đơn giản đâu nha!
— Anh Lead
Mình sẽ thử viết câu query với yêu cầu của anh lead, nó sẽ như sau
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | <span class="token operator">></span> <span class="token keyword">SELECT</span> <span class="token operator">*</span> <span class="token keyword">FROM</span> <span class="token punctuation">`</span>categories<span class="token punctuation">`</span> <span class="token keyword">WHERE</span> <span class="token punctuation">`</span>parent_id<span class="token punctuation">`</span> <span class="token operator">IN</span> <span class="token punctuation">(</span><span class="token keyword">SELECT</span> <span class="token punctuation">`</span>id<span class="token punctuation">`</span> <span class="token keyword">FROM</span> <span class="token punctuation">`</span>categories<span class="token punctuation">`</span> <span class="token keyword">WHERE</span> <span class="token punctuation">`</span>parent_id<span class="token punctuation">`</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token comment">-----------------------------------------------</span> <span class="token operator">|</span> id <span class="token operator">|</span> <span class="token keyword">value</span> <span class="token operator">|</span> parent_id <span class="token operator">|</span> <span class="token comment">-----------------------------------------------</span> <span class="token operator">|</span> <span class="token number">2</span> <span class="token operator">|</span> Lập trình web <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> Lập trình mobile <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">4</span> <span class="token operator">|</span> Backend <span class="token operator">|</span> <span class="token number">2</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">5</span> <span class="token operator">|</span> Frontend <span class="token operator">|</span> <span class="token number">2</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">6</span> <span class="token operator">|</span> Progresstive web app <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">7</span> <span class="token operator">|</span> Hybrid app <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">8</span> <span class="token operator">|</span> Native app <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> <span class="token comment">-----------------------------------------------</span> |
Đến đây mình nhận thấy vấn đề, cụ thể chúng ta cần biết danh mục cha đang ở cấp thứ mấy để dùng câu lệnh WHERE..IN (hoặc JOIN) với số lần tương ứng (cụ thể ở câu query trên cần 1 lần) và đương nhiên không thể ngồi đếm thứ cấp của tụi này khi data lớn lên được. OK Fine! It’s time to googling!
Cấu trúc dữ liệu: cây – tree
Sau khi đã google ra thông tin cần thiết, mình chọn materialized path pattern để áp dụng lưu trữ dạng data này, nguyên lí hoạt động khá đơn giản: chúng ta sẽ thêm vào 1 cột trong bảng để lưu đường dẫn của node hiện tại.
Mình không nói sâu hơn về cây (tree) mà đi thẳng vào cách áp dụng luôn (để cho người đọc dễ hình dung hơn và ít lí thuyết hơn, chúng ta sửa lại schema như sau:
1 2 3 4 5 6 7 8 | <span class="token keyword">CREATE</span> <span class="token keyword">TABLE</span> <span class="token keyword">IF</span> <span class="token operator">NOT</span> <span class="token keyword">EXISTS</span> <span class="token punctuation">`</span>categories<span class="token punctuation">`</span> <span class="token punctuation">(</span> <span class="token punctuation">`</span>id<span class="token punctuation">`</span> <span class="token keyword">int</span><span class="token punctuation">(</span><span class="token number">6</span><span class="token punctuation">)</span> <span class="token keyword">unsigned</span> <span class="token keyword">AUTO_INCREMENT</span> <span class="token operator">NOT</span> <span class="token boolean">NULL</span><span class="token punctuation">,</span> <span class="token punctuation">`</span><span class="token keyword">value</span><span class="token punctuation">`</span> <span class="token keyword">varchar</span><span class="token punctuation">(</span><span class="token number">255</span><span class="token punctuation">)</span> <span class="token operator">NOT</span> <span class="token boolean">NULL</span><span class="token punctuation">,</span> <span class="token punctuation">`</span>parent_id<span class="token punctuation">`</span> <span class="token keyword">int</span><span class="token punctuation">(</span><span class="token number">6</span><span class="token punctuation">)</span> <span class="token keyword">unsigned</span> <span class="token boolean">NULL</span><span class="token punctuation">,</span> <span class="token keyword">PRIMARY</span> <span class="token keyword">KEY</span> <span class="token punctuation">(</span><span class="token punctuation">`</span>id<span class="token punctuation">`</span><span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token keyword">FOREIGN</span> <span class="token keyword">KEY</span> <span class="token punctuation">(</span><span class="token punctuation">`</span>parent_id<span class="token punctuation">`</span><span class="token punctuation">)</span> <span class="token keyword">REFERENCES</span> categories<span class="token punctuation">(</span><span class="token punctuation">`</span>id<span class="token punctuation">`</span><span class="token punctuation">)</span> <span class="token keyword">ON</span> <span class="token keyword">DELETE</span> <span class="token keyword">CASCADE</span> <span class="token punctuation">)</span> <span class="token keyword">DEFAULT</span> <span class="token keyword">CHARSET</span><span class="token operator">=</span>utf8<span class="token punctuation">;</span> |
Sau khi seed lại dữ liệu tương tự như ban đầu, ta được
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | <span class="token operator">></span> <span class="token keyword">SELECT</span> <span class="token operator">*</span> <span class="token keyword">FROM</span> <span class="token punctuation">`</span>categories<span class="token punctuation">`</span> <span class="token comment">-----------------------------------------------</span> <span class="token operator">|</span> id <span class="token operator">|</span> <span class="token keyword">value</span> <span class="token operator">|</span> path <span class="token operator">|</span> <span class="token comment">-----------------------------------------------</span> <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> Lập trình căn bản <span class="token operator">|</span> <span class="token operator">/</span><span class="token number">1</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">2</span> <span class="token operator">|</span> Lập trình web <span class="token operator">|</span> <span class="token operator">/</span><span class="token number">1</span><span class="token operator">/</span><span class="token number">2</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> Lập trình mobile <span class="token operator">|</span> <span class="token operator">/</span><span class="token number">1</span><span class="token operator">/</span><span class="token number">3</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">4</span> <span class="token operator">|</span> Backend <span class="token operator">|</span> <span class="token operator">/</span><span class="token number">2</span><span class="token operator">/</span><span class="token number">4</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">5</span> <span class="token operator">|</span> Frontend <span class="token operator">|</span> <span class="token operator">/</span><span class="token number">2</span><span class="token operator">/</span><span class="token number">5</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">6</span> <span class="token operator">|</span> Progresstive web app <span class="token operator">|</span> <span class="token operator">/</span><span class="token number">3</span><span class="token operator">/</span><span class="token number">6</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">7</span> <span class="token operator">|</span> Hybrid app <span class="token operator">|</span> <span class="token operator">/</span><span class="token number">3</span><span class="token operator">/</span><span class="token number">7</span> <span class="token operator">|</span> <span class="token operator">|</span> <span class="token number">8</span> <span class="token operator">|</span> Native app <span class="token operator">|</span> <span class="token operator">/</span><span class="token number">3</span><span class="token operator">/</span><span class="token number">8</span> <span class="token operator">|</span> <span class="token comment">-----------------------------------------------</span> |
Các bạn có hình dung được cách cài đặt của pattern này chưa? Giờ thì mình cùng query vài câu xem nhé. Chúng ta sẽ giải quyết vấn đề của cách cũ bằng câu query sau:
SELECT * FROM
categoriesWHEREpathLIKE ‘/1/%’
Yeah! Câu query đã được ngắn gọn đi rất nhiều và đặc biệt dù cây danh mục của chúng ta có bao nhiêu cấp và đang tìm ở cấp nào thì chỉ việc thay ‘/1/%’ thành ‘path%’ với path của danh mục hiện tại là xong
Kết luận
Mặc dùng CTDL là 1 thứ gì đó khá là khoai đối với sinh viên khi nghe giảng ở trường nhưng không thể phủ nhận được tính ứng dụng thực tiễn tuyệt với mà nó mang lại, vậy nên các bạn sinh viên hãy học tốt môn này nhé, nếu cấu trúc cây mà chưa không biết thì nên học ngay vì nó còn ứng dụng nhiều thứ khác nữa đấy. Happy coding!~
Tham khảo
[1] http://www.dba-oracle.com/t_sql_patterns_trees.htm
[2] https://bojanz.wordpress.com/2014/04/25/storing-hierarchical-data-materialized-path/
Bài viết được trích từ blog mình, nếu thấy hay các bạn vào blog https://phatng.com/ ủng hộ mình nhé