Cấu trúc dữ liệu và Giải thuật Bài 2: RAM Model: Cách máy tính lưu trữ và xử lý dữ liệu ở tầng bộ nhớ.

Để thực sự làm chủ Cấu trúc dữ liệu, chúng ta cần tạm quên đi những dòng code trừu tượng ở tầng ngôn ngữ lập trình và nhìn sâu vào nơi mọi thứ thực sự diễn ra: Bộ nhớ vật lý của máy tính (RAM).

Dù bạn đang viết code bằng PHP, Golang, hay điều khiển vi điều khiển bằng C/C++, hệ điều hành và CPU đều nhìn dữ liệu của bạn dưới cùng một lăng kính. Đó chính là Mô hình RAM (Random Access Memory Model).

1. RAM: Thành phố của những ô nhớ

Hãy tưởng tượng RAM của bạn là một tòa chung cư khổng lồ với hàng tỷ hộp thư nhỏ xếp cạnh nhau. Mỗi hộp thư có một địa chỉ (Address) duy nhất (thường được biểu diễn dưới dạng Hexadecimal, ví dụ: 0x7ffcd9c).

Mỗi hộp thư này có thể chứa đúng 1 Byte (8 bits) dữ liệu.

• Nếu bạn khai báo một biến boolean, nó có thể chỉ chiếm 1 ô nhớ.

• Nếu bạn khai báo một biến số nguyên int32 (như trong Golang hay C++), nó sẽ cần một khối gồm 4 ô nhớ nằm liền kề nhau (4 Bytes).

• Nếu bạn khai báo int64, nó cần 8 ô nhớ liền kề.

Khi bạn chạy chương trình, hệ điều hành sẽ tìm những khối hộp thư còn trống và cấp phát cho các biến của bạn.

2. Quyền năng tối thượng của "Random Access" (Truy cập ngẫu nhiên)

Từ "Random" ở đây không có nghĩa là lộn xộn. Nó mang một ý nghĩa cực kỳ quan trọng trong khoa học máy tính: Thời gian truy cập vào bất kỳ ô nhớ nào là như nhau, bất kể địa chỉ của nó ở đầu hay ở cuối thanh RAM.

• Viết dữ liệu vào ô nhớ số 0x000001 mất $O(1)$ thời gian.

• Đọc dữ liệu ở ô nhớ số 0xFFFFFF cũng chỉ mất $O(1)$ thời gian.

Nhờ tính chất này, hệ thống không cần phải duyệt từ đầu bộ nhớ để tìm đến cuối bộ nhớ. Chỉ cần biết chính xác địa chỉ, CPU có thể lấy dữ liệu ra ngay lập tức. Đây là nền tảng cốt lõi giải thích tại sao mảng (Array) hay Bảng băm (Hash Table) lại có khả năng truy xuất thần tốc.

3. Contiguous Memory (Bộ nhớ liên tục) và Pointers (Con trỏ)

Hiểu về RAM Model giúp bạn giải mã được bản chất thực sự của các cấu trúc dữ liệu cơ bản. Hãy lấy Mảng (Array) làm ví dụ.

Khi bạn khai báo một mảng gồm 5 số nguyên int32, máy tính không vứt 5 số này ở 5 nơi khác nhau. Nó tìm một dải gồm 20 ô nhớ nằm sát cạnh nhau (5 phần tử * 4 Bytes) và đánh dấu đó là mảng của bạn.

Ví dụ thực tế trong Go/C++:

Giả sử phần tử đầu tiên arr[0] nằm ở địa chỉ 0x1000.

Vì bạn biết mỗi phần tử chiếm 4 Bytes, máy tính có thể lập tức tính ra địa chỉ của arr[3] bằng một công thức toán học vô cùng đơn giản:

Địa chỉ arr[3] = Địa chỉ arr[0] + (3 * 4 Bytes) = 0x1012.

Đó là lý do thao tác đọc arr[3] chỉ mất $O(1)$. Máy tính không cần duyệt qua arr[1] và arr[2], nó nhảy vọt thẳng đến 0x1012 dựa vào toán học con trỏ (Pointer Arithmetic).

Ngược lại, với Danh sách liên kết (Linked List), các phần tử nằm rải rác khắp nơi trong RAM. Phần tử trước phải "cầm" địa chỉ của phần tử sau. Để đến được node thứ 3, CPU bắt buộc phải ghé thăm node 1, đọc địa chỉ node 2, ghé thăm node 2, rồi mới tới được node 3. Đây là lý do truy xuất Linked List tốn $O(n)$ thời gian.

4. Tại sao Mảng luôn nhanh hơn Danh sách liên kết trên thực tế? (Spatial Locality)

Về mặt lý thuyết Big-O, một số thao tác trên Mảng và Linked List có cùng độ phức tạp. Nhưng trong thực tế, nếu bạn benchmark trên một hệ thống như server xử lý giao dịch hoặc chạy firmware, Mảng luôn vượt trội về tốc độ. Tại sao?

Câu trả lời nằm ở CPU Cache (Bộ nhớ đệm L1/L2/L3) và tính Cục bộ không gian (Spatial Locality).

Tốc độ của RAM nhanh hơn ổ cứng (SSD/HDD) rất nhiều, nhưng so với CPU, RAM vẫn là một "con rùa". Để tối ưu, CPU có một bộ nhớ Cache rất nhỏ nhưng siêu nhanh nằm ngay trong lõi của nó.

Khi CPU cần đọc arr[0] từ RAM, nó không chỉ lấy mỗi arr[0]. Với tư duy "tiện đường", hệ thống phần cứng sẽ bốc luôn một mảng dữ liệu liền kề (gọi là Cache Line, thường là 64 Bytes) lên CPU Cache, bao gồm cả arr[1], arr[2], arr[3]....

• Với Mảng: Các phần tử nằm sát nhau. Khi CPU cần arr[1], dữ liệu đã có sẵn trên siêu tốc độ của CPU Cache (Cache Hit). Mã nguồn thực thi gần như tức thì.

• Với Linked List: Các phần tử rải rác. CPU bốc một khối dữ liệu xung quanh Node 1 lên Cache, nhưng Node 2 lại nằm ở một phương trời khác. CPU đành phải "lóc cóc" chạy xuống RAM để tìm tiếp (Cache Miss). Việc liên tục Cache Miss khiến hiệu năng của chương trình giảm sút nghiêm trọng.

RAM Model cho thấy: Việc chọn đúng Cấu trúc dữ liệu không chỉ là câu chuyện của những dòng code trừu tượng, mà là nghệ thuật làm việc hài hòa với quy luật vật lý của phần cứng.

Khi đã nắm rõ cách bộ nhớ làm việc trong thời gian hằng số $O(1)$, chúng ta đã có đủ cơ sở để chính thức bước vào việc đo lường hiệu năng của mọi thuật toán trên đời. Ở bài học tiếp theo, chúng ta sẽ bắt tay vào phân tích Độ phức tạp thời gian và Ký pháp Big-O.