images
21/10/2020 09:30 am

SQL Indexing để tăng tốc độ tìm kiếm với BTree

SQL Index là cách SQL tăng tốc việc truy vấn dữ liệu thông qua việc đánh chỉ mục các dữ liệu trong bảng. Nôm na giống như bạn đọc sách và muốn tra cứu thì bạn giở phần mục lục cuối trang để tra cứu tới trang muốn tìm kiếm một cách nhanh hơn.

SQL Index


SQL Index là cách SQL tăng tốc việc truy vấn dữ liệu thông qua việc đánh chỉ mục các dữ liệu trong bảng. Nôm na giống như bạn đọc sách và muốn tra cứu thì bạn giở phần mục lục cuối trang để tra cứu tới trang muốn tìm kiếm một cách nhanh hơn.


Bạn hình dung khi bạn có một bảng dữ liệu tới vài triệu record khách hàng và muốn tìm một khách hàng nào đó theo tên. Việc tìm kiếm được thực hiện tuần tự bằng cách so sánh từng phần tử của record trong bảng sẽ mất thời gian và tốn chi phí tính toán. 


Tìm kiếm tuần tự


Việc tìm kiếm tuần tự còn gọi là việc scan. Ta sẽ lần lượt kiểm tra từng record của danh sách N phần tử để tìm ra phần tử đúng với phần tử K đang tìm kiếm:


Tối đa ta phải quét N phần tử. Trong trường hợp này độ phức tạp thuật toán là O(n). 


Tìm kiếm trên data đã được sắp xếp


Việc tìm kiếm trên dữ liệu chưa được sắp thứ tự thì chậm hơn nhiều lần so với tìm kiếm trên dữ liệu đã được sắp xếp. Với dữ liệu đã sắp xếp, ta sẽ tìm kiếm từ giữa danh sách. Thực hiện so sánh với phần tử ở giữa, nếu phần tử tìm kiếm nhỏ hơn thì ta tìm ở nửa bên trái, nếu phần tử tìm kiếm lớn hơn thì ta tìm ở vị trí nửa bên phải. Thuật toán tiếp tục lặp lại để tìm ra kết quả:


Trong trường hợp này độ phức tạp thuật toán là O(log(n)). 


BTree là gì?


Việc tìm kiếm trên một data đã sắp xếp thì tốc độ nhanh hơn nhiều lần. Tuy nhiên tốc độ (time) khi chúng ta thêm mới phần tử hoặc chỉnh sửa, thì lại chậm đi. Đó là lí do ra đời BTree.


BTree là thuật toán index dữ liệu được đưa ra vào năm 1970 được đưa ra bởi Rudolf Bayer and Edward M.McCreight. Mục đích là đánh chỉ mục cho các trang dữ liệu nằm trên số lượng lớn các file dữ liệu. Để tăng tốc độ thì dữ liệu cần lưu trên RAM, tuy nhiên trên RAM thì bộ nhớ có giới hạn. Do đó cần cách tổ chức lưu trữ hiệu quả cho việc tìm kiếm. 


BTree là cấu trúc dữ liệu được phân cấp theo hình cây (tree) bao gồm node gốc (root), node giữa (internal) và node lá (leaves). Dữ liệu được tổ chức có sắp xếp theo thứ tự tăng dần. Nó là dạng tổng quát của cây nhị phân, với cây nhị phân thì mỗi node có 2 node con. BTree được gọi là self balancing tree với mỗi node có thể có nhiều hơn 2 node con.


Minh họa BTree


Đây là minh hoạ một BTree bậc m = 3:

Các ô tròn xanh là node. Số trong ô gọi là key.

Các key được sắp tăng dần từ trái qua phải




BTree được implement theo nhiều cách khác nhau. Theo wikipedia, thuật toán được Knuth (Tác giả cuốn Art of Programming) mô tả một BTree bậc m (m-degree) là:

- Mỗi node có nhiều nhất m node con

- Mỗi node không phải là node lá (leaves) có ít nhất m/2 node con

- Node gốc (root) có ít nhất 2 node con

- Node có chứa k node con thì chứa k-1 key. Key này sẽ quyết định các sub-tree của node đó. 


Ví dụ 1 node có 2 key là: a1 và a2 thì dưới node đó sẽ có 3 sub-tree con: sub-tree bên trái chứa key nhỏ hơn a1, sub-tree ở giữa chứa key nằm giữa a1-a2, sub-tree bên phải chứa key lớn hơn a2.


Thay đổi BTree


- Đặc điểm của BTree là khi bạn thêm mới hoặc xóa đi dữ liệu, BTree sẽ được tổ chức lại để phù hợp với dữ liệu mới. Do đó khác với các tổ chức thông thường, BTree sẽ chậm hơn trong việc thêm mới hoặc sửa đổi, nhưng đáp ứng tốc độ nhanh hơn nhiều khi truy vấn.


- Thuật toán BTree được áp dụng cho việc đánh chỉ mục trong database nhằm tăng tốc độ tìm kiếm. Việc đánh chỉ mục bạn có thể hiểu giống như đánh mục lục cho trang sách vậy, nó giúp chúng ta tìm kiếm nhanh hơn thay vì phải lật từng trang sách. Trước tiên là hãy cùng tìm hiểu rõ thuật toán này.


Lưu ý: Số lượng key ở mỗi node tuỳ vào từng implementation cụ thể. Mỗi một RDBMS có thể có cách cài đặt khác nhau về số bậc và số key mỗi node.


Minh họa BTree


Giả sử ta biểu diễn dãy số sau dạng BTree: 10, 43, 26, 4, 17. Dưới dây là các bước thay đổi của BTree khi thêm dữ liệu:

- Các phần tử thêm ở bên phải nếu lớn hơn, bên trái nếu nhỏ hơn

- Số key trên mỗi node tối đa là 2


Tiếp tục thêm vào dãy số số 4 và 17. Tree sẽ được balancing sau mỗi bước:

Kết quả: Ta luôn có danh sách tăng dần từ trái sang phải.


Giả sử biểu diễn dãy số sau dạng BTree: 10, 43, 26, 4, 17, Thêm 18:

Khi thêm 20 vào mảng: 10, 43, 26, 4, 17, 18. Add 20 theo đường đỏ:


Ta thêm 20 vào mảng: 10, 43, 26, 4, 17, 18. Cây sẽ được rebalancing như sau:

Kết quả: 4,10,1,18,20,26,43


BTree Performance


Chúng ta hãy xem bảng dưới đây về độ phức tạp của từng thuật toán ở các bước thêm mới - xóa và tìm kiếm.


Hành động

Thêm mới

Xóa

Tìm kiếm

Danh sách không sắp xếp

O(1)

O(n)

O(n)

Danh sách có sắp xếp

O(n)

O(n)

O(log(n))

B-tree

O(log(n))

O(log(n))

O(log(n))


Tìm kiếm với BTree


Tìm kiếm 20 trong BTree: 

Ta so sánh với key ở gốc, nếu lớn hơn thì di chuyển sang phải, nhỏ hơn thì di chuyển sang trái, kết quả tìm được sau 3 bước:

BTree Performance


Về cơ bản, chúng ta thấy rằng, dữ liệu thường có thao tác đọc - nhiều hơn nhiều lần so với thao tác ghi. Do đó với BTree, dù việc ghi dữ liệu có chậm đi một chút, thì lại đem lại tốc độ tốt hơn khi đọc. Tất nhiên ở đây ta đang đánh đổi 2 khía cạnh là time và space. Để tiết kiệm time khi truy vấn thì ta cần space để tổ chức dữ liệu dễ tìm kiếm.


BTree Index trong Database


Trong SQL, để tìm kiếm với INDEX cho một giá trị nào đó của cột thì ta cần phải tạo index trên cột đó. Giả sử ta có table Customer sau:


ID

Name

1

John

2

Allen

3

Teddy

4

Ken

5

Luke

7

Michael

8

Rose

9

Cold

10

Young


Nhu cầu là chúng ta muốn tăng tốc việc tìm kiếm khách hàng theo tên, tức truy vấn dựa trên cột Name. 


Biểu diễn BTree cho bảng với cột Name, thứ tự sắp xếp là theo Name.


Mỗi node chứa giá trị name và id của row. Như vậy khi tìm được theo tên, ta có thể tìm được row theo ID

B+Tree Index trong Database


Để tìm row theo ID nhanh nhất, Database sẽ thêm một BTree mới sắp xếp theo giá trị ID và gọi là B+Tree, trong đó các node lá sẽ chứa toàn bộ giá trị của row kèm thông tin ID. 

Các Node lá màu Tím chứa rowid và data thực sự của record.


Như vậy trình tự tìm kiếm Name sẽ như sau:

1. Sử dụng BTree để tìm Name và RowID

2. Sử dụng B+Tree Index để tìm đầy đủ record của ROW này.



Áp dụng thực tế: Ta có bảng products gồm các thông tin sau, tổng số record là > 1 triệu bản ghi:


Ta cần tìm kiếm product theo title. Ví dụ: tìm product :


select * from products where title = 'Awesome Plastic Watch'

Câu truy vấn này chạy hết:  198ms



Sequence Scan


Xem chi tiết execution plan: Ta thấy câu truy vấn phải chạy tuần tự (sequence scan hoặc có thể gọi với tên khác là full-scan) với chi phí 27924, chi phí này là đại lượng tính theo time, cpu, io… để chạy câu truy vấn.


SQL Query với index


Giờ ta sẽ tạo ra index trên cột title như sau:


CREATE INDEX title_idx ON products (title)


Câu truy vấn này chạy hết:  59ms nhanh gấp 3 lần


select * from products where title = 'Awesome Plastic Watch'



Index Scan

Xem chi tiết execution plan:

Ta thấy câu truy vấn phải có chi phí thấp hơn nhiều do dùng index.


Kết luận:

Chúng ta vừa tìm hiểu về BTree Index và cách sử dụng index cơ bản trên 1 cột dữ liệu để tăng tốc độ truy vấn trong cơ sở dữ liệu.


Mời các bạn xem thêm Các bài giảng SQL của Tech Zone.


- Tech Zone -

Thư giãn chút nào!!!

Bài viết liên quan