Biến thể B-tree mới cho bộ nhớ Nand flash

168 KỶ YẾU HỘI THẢO KHOA HỌC QUỐC GIA CITA 2017 “CNTT VÀ ỨNG DỤNG TRONG CÁC LĨNH VỰC” Biến thể B-tree mới cho bộ nhớ Nand flash Hồ Văn Phi1, Nguyễn Văn Lợi2 1,2 Khoa Công nghệ thông tin, Trường CĐ CNTT hữu nghị Việt - Hàn phihv@viethanit.edu.vn, loinv@viethanit.edu.vn Abstract. Bộ nhớ flash được sử dụng rất phổ biến hiện nay do những ưu điểm nổi bật của loại bộ nhớ này như tốc độ nhanh, gọn nhẹ, tính ổn định cao, tiêu thụ ít điện năng. Tuy nhiên, bên cạnh những ưu điểm nổi bật nói trên bộ nhớ flash vẫn có những nhược điểm đáng chú ý như thuộc tính “Erase-before-write” (xóa dữ liệu trước khi ghi vào một ô nhớ cụ thể), vòng đời hữu hạn (số lần xóa hạn chế -khoảng 10.000~100.000 lần). Những nhược điểm này khiến cho việc triển khai cây chỉ mục B-tree trên bộ nhớ flash giảm hiệu quả đáng kể bởi vì một số lượng lớn các thao tác trên bộ nhớ flash được thực hiện mỗi khi cập nhật dữ liệu trên cây B-tree. Nghiên cứu này giới thiệu một biến thể mới của cây B-tree cho bộ nhớ flash gọi là OMB. Biến thể này giúp làm giảm số lượng các thao tác trên bộ nhớ flash đồng thời tăng hiệu suất sử dụng của bộ nhớ flash do đó tuổi thọ của bộ nhớ flash sẽ được tăng lên. Keywords: Chỉ mục B-tree, bộ nhớ flash, cây B-tree trên flash. 1 Giới thiệu Bộ nhớ Flash [1-2] được sử dụng rất phổ biến hiện nay nhờ vào những ưu điểm nổi bật của chúng như tốc độ cao, tiêu thụ ít điện năng, kích thước nhỏ gọn và độ an toàn dữ liệu cao. Tuy nhiên, bên cạnh những điểm mạnh đó, bộ nhớ flash vẫn có những điểm yếu cần lưu tâm đó là đặc tính “xóa trước khi ghi” (erase-before-write - không thể ghi đè (overwrite)) và vòng đời hữu hạn (khoảng từ 10.000 đến 100.000 lần xóa trên mỗi block). Bộ nhớ flash có cấu tạo và cơ chế hoạt động hoàn toàn khác với đĩa cứng (HDD) thông thường. Do đó để giúp các hệ điều hành truy cập bộ nhớ flash một cách tương tự như HDD, một phần mềm trung gian có tên là FTL[1] (Flash Translation Layer) được sử dụng để chuyển đổi địa chỉ logic sang địa chỉ vật lý ánh xạ giữa máy tính và bộ nhớ flash. FTL có 3 chức năng chính đó là: ánh xạ địa chỉ (Address mapping), thu hồi khối nhớ không hợp lệ (Gabbage collection) và điều phối ghi dữ liệu trên các khối nhớ (Wear leveling). Chức năng ánh xạ địa chỉ cung cấp các thuật toán ánh xạ giữa địa chỉ logic và địa chỉ vật lý trên bộ nhớ flash. Đã có rất nhiều thuật toán ánh xạ địa chỉ được giới thiệu. Chúng có thể được gom thành 3 nhóm chính: Ánh xạ sector (Sector mapping), ánh xạ khối (Block mapping) và ánh xạ lai (Hybrid mapping). Gabbage collection có chức năng thu hồi các khối nhớ không hợp lệ để tái sử dụng. Khi số lượng khối nhớ hợp lệ trên bộ nhớ flash thấp hơn ngưỡng cho phép, gabbage collection sẽ được tự động kích hoạt để thu hồi và tái sử dụng các khối không hợp lệ. Wear leveling được sử dụng để điều tiết các khối nhớ để đảm bảo các khối nhớ có tần suất được sử dụng là tương đương nhau. Wear leveling sẽ quyết định khối nhớ nào được sử dụng khi có yêu cầu ghi dữ liệu vào bộ nhớ flash. Mặc dù hiệu suất của bộ nhớ flash tăng đáng kể bằng cách sử dụng các thuật toán FTL, tuy nhiên, việc triển khai cây chỉ mục B-tree trên bộ nhớ flash vẫn bị giảm đáng kể do một số lượng lớn các thao tác (read/write/erase) trên bộ nhớ flash được thực hiện mỗi khi cập nhật dữ liệu trên Hồ Văn Phi, Nguyễn Văn Lợi 169 cây B-tree. Để giải quyết vấn đề này, đã có nhiều lược đồ cây chỉ mục B-tree cho bộ nhớ flash được giới thiệu. Tuy nhiên, những lược đồ đó vẫn tồn tại một số nhược điểm như giảm hiệu suất hoạt động và vòng đời của bộ nhớ flash hoặc nguy cơ mất dữ liệu khi nguồn điện bị cắt đột ngột. Nghiên cứu này giới một biến thể mới của cây chỉ mục B-tree cho bộ nhớ flash gọi lại OMB. Biến thể có cơ chế tách nút khác với cây chỉ mục B-tree nguyên mẫu gọi là cơ chế tràn. Nếu một nút lá được điền đầy bởi các giá trị khóa liên tiếp thì toàn bộ nút đó được ghi vào bộ nhớ thay vì tách thành 2 nút khác nhau như cây B-tree nguyên thủy. Ngoài ra, khi một nút có số lượng giá trị khóa giữa ngưỡng cho phép, nút đó vẫn giữ nguyên mà không phải bị ghép với các nút anh em lân cận của nó. Cơ chế tràn giúp cho biến thể mới này giảm một số lượng đáng kể các thao tác của bộ nhớ flash. Bên cạnh đó nó cũng giúp cho việc sử dụng không gian nhớ trong các khối nhớ cũng đạt hiệu suất cao. Kết quả thử nghiệm cho thấy giải pháp mới này giúp cho việc triển khai cây chỉ mục B-tree trên bộ nhớ flash có hiệu quả cao, tiết kiệm được không gian nhớ và kéo dài tuổi thọ của bộ nhớ flash bởi vì OMB làm giảm số lượng thao tác xóa của bộ nhớ flash. 2 Kiến thức cơ bản và nghiên cứu liên quan Flash là một loại thiết bị bộ nhớ thứ cấp được sử dụng rất phổ biến hiện nay. Chúng có mặt trong các thiết bị điện tử như máy tính, điện thoại thông minh, các thiết bị nhúng, thẻ nhớ, USB,... Khác với đĩa cứng thông thường, bộ nhớ flash gồm một dãy các thẻ nhớ Nand flash. Bộ nhớ flash được tổ chức thành các khối nhớ; mỗi khối nhớ chứa một số lượng cụ thể các trang nhớ (32, 64, 128 trang). Trang nhớ là đơn vị nhỏ nhất của thao tác đọc và ghi trong khi đó khối nhớ là đơn vị nhỏ nhất của thao tác xóa. Bộ nhớ flash hỗ trợ 3 thao tác cơ bản là đọc, ghi và xóa. Đọc là thao tác có tốc độ nhanh nhất tiếp đến là thao tác ghi. Một thao tác ghi mất khoảng 2ms; chậm hơn 10 lần so với thao tác đọc. Và chậm nhất là thao tác xóa, chậm hơn 10 lần so với thao tác ghi. Hiện nay, bộ nhớ flash có vòng đời khoảng 10.000 - 100.000 lần xóa khối. Nếu số lần xóa của một khối vượt quá ngưỡng này thì khối đó không còn khả năng sử dụng. Cây chỉ mục B-tree là một cấu trúc dữ liệu được sử dụng rộng rãi trong các hệ quản trị cơ sở dữ liệu và hệ điều hành nhờ vào tốc độ truy cập nhanh của nó. Tuy nhiên, tần suất cập nhật và ghi dữ liệu ngẫu nhiên trên cây B-tree rất lớn nên hiệu quả của cây B-tree trên bộ nhớ flash sẽ giảm đáng kể. Như đã đề cập ở trên, bên cạnh những điểm mạnh nổi bật, bộ nhớ flash có hai nhược điểm lớn đó là đặc tính xóa trước khi ghi và hạn chế số lần xóa khối. Do đó, nếu triển khai một cây B-tree nguyên thủy trên bộ nhớ flash sẽ dẫn đến hiệu quả hoạt động thấp. Hình 1 trình bày một ví dụ về việc triển khai cây chỉ mục B-tree trên bộ nhớ flash sử dụng thuật toán ánh xạ địa chỉ Block mapping. Hình 1. Ví dụ B-tree trên bộ nhớ flash 170 KỶ YẾU HỘI THẢO KHOA HỌC QUỐC GIA CITA 2017 “CNTT VÀ ỨNG DỤNG TRONG CÁC LĨNH VỰC” Giả sử mỗi nút của cây được lưu trữ trong 1 trang nhớ của bộ nhớ flash. Nếu một bản ghi với giá trị khóa 12 được chèn vào cây B-tree thì yêu cầu cập nhật trên nút C và ghi dữ liệu trên trang nhớ của bộ nhớ flash. Vì đặc tính xóa trước khi ghi (không thể ghi đè) nên quá trình chèn 12 được thực hiện như sau: Đầu tiên các nút hợp lệ (A, B) trong block #n được sao chép sang block #m; ghi nút C’ vào block #m và cuối cùng block #n sẽ bị xóa hoặc đánh dấu block không hợp lệ. Quá trình này phát sinh rất nhiều các thao tác trên flash được dẫn đến giảm hiệu suất và vòng đời của flash. Để giải quyết vấn đề này, một số lược đồ cây B-tree cho bộ nhớ flash đã được đề xuất. Các lược đồ này có thể chia thành 3 nhóm chính đó là: Nhóm sử dụng bộ đệm (RAM), nhóm thay đổi cấu trúc và nhóm lai. Nhóm sử dụng bộ đệm [4-7] sử dụng một phần bộ nhớ RAM của hệ thống để làm bộ đệm. Mọi thay đổi trên cây B-tree đề được ghi vào bộ đệm. Khi bộ đệm đầy, dữ liệu trên bộ đệm sẽ được ghi vào cây B-tree trên bộ nhớ flash. Ưu điểm của nhóm này là tốc độ nhanh. Tuy nhiên, nhược điểm lớn của nó là nguy cơ mất dữ liệu cao do dữ liệu ghi tạm trên bộ đệm là RAM. Nếu nguồn cấp bị ngắt đột ngột, toàn bộ dữ liệu trên bộ đệm sẽ bị mất. Mặt khác do chúng sử dụng RAM làm bộ đệm nên rất khó áp dụng trên các hệ thống nhúng nhỏ vì các hệ thống nhúng này thường có dung lượng RAM hạn chế. Đối với nhóm thay đổi cấu trúc [8-14], cấu trúc của cây B-tree trong nhóm này được thay đổi để phù hợp với cơ chế hoạt động của bộ nhớ flash. Dữ liệu trong một nút của cây có thể được lưu trữ trên hai vùng nhớ khác nhau gọi là data block và buffer block. Khi buffer block đầy, dữ liệu của cây trên data block sẽ trộn với dữ liệu trên buffer block. Ưu điểm của nhóm này là dữ liệu của cây luôn luôn được đảm bảo vì đã được lưu trên bộ nhớ flash. Tuy nhiên, nhược điểm là chúng phát sinh thêm một số lượng lớn các thao tác đọc, ghi, xóa trên bộ nhớ flash do phải thao tác dữ liệu trên các buffer block. Do đó, hiệu suất của nhóm này thường không cao và làm giảm tuổi thọ của bộ nhớ flash. Thừa hưởng ưu điểm và hạn chế nhược điểm của hai nhóm trên, nhóm lai [15-16] sử dụng kết hợp cả hai giải pháp trên. Chúng sử dụng bộ đệm (RAM) và buffer block để lưu trữ dữ liệu tạm thời. Mỗi ghi dữ liệu được ghi vào bộ đệm thì chúng cũng được ghi đồng thời vào buffer block. Khi bộ đệm đầy dữ liệu trên bộ đệm sẽ được ghi vào data block đồng thời đánh dấu đã ghi dữ liệu thành công vào buffer block. Ưu điểm của nhóm này là không bị mất dữ liệu. Nhược điểm của chúng là làm tăng số lượng thao tác trên bộ nhớ flash và tiêu tốn tài nguyên RAM của hệ thống. 3 OMB: Cơ chế tràn cho cây B-tree Phần này giới thiệu một cơ chế hoạt động mới cho cây chỉ mục B-tree trên bộ nhớ flash gọi là OMB để triển khai cây B-tree trên bộ nhớ flash đạt hiệu quả cao. Mục tiêu của nó là làm giảm đáng kể một số lượng lớn các thao tác trên bộ nhớ flash (read, write, erase) khi xây dựng cây B-tree và năng cao hiệu quả trong việc sử dụng không gian trong các trang nhớ để lưu trữ cây B-tree. Cơ chế tràn hoạt động như sau: khi một bản ghi được chèn vào một nút của cây B-tree, OMB sẽ kiểm tra nút đó có bị tràn hay không. Nếu nút đó chưa đầy thì thì bản ghi được chèn vào nút. Ngược lại, nếu nút đã đầy, OMB sẽ kiểm tra xem các giá trị khóa của nút đó được chèn một cách tuần tự các giá trị liên tiếp hay không. Nếu nút được chèn đầy bởi các giá trị không liên tiếp thì nút sẽ được tách thành 2 nút khác nhau giống như việc tách nút trên cây B-tree nguyên thủy. Ngược lại, nếu các giá trị khóa là liên tiếp thì nút được ghi trực tiếp vào bộ nhớ flash mà Hồ Văn Phi, Nguyễn Văn Lợi 171 không cần phải tách nút như cây B-tree thông thường. Cơ chế này được minh họa bằng hình ảnh dưới đây. Hình 2. Ví dụ về cơ chế tràn Trong ví dụ này, nút D có 4 khóa lần lượt là 12, 13, 14 và 15. Đối với cây B-tree nguyên thủy, bản ghi với giá trị khóa 20 khi được chèn vào cây thì nút D sẽ tràn và bị tách thành 2 nút khác nhau D và E như hình (b). Một nữa các giá bên trái của nút D (12, 13) được giữ nguyên ở trong nút D và nữa còn lại (14, 15) cùng với giá trị mới chèn vào (20) sẽ tạo nên một nút mới (E). Đồng thời giá trị giữa của nút (14) được chèn vào nút cha của nó là nút A. Việc này có thể dẫn đến việc tràn và tách nút cha và cứ như vậy cho đến nút gốc. Nếu nút tràn không có nút cha thì một nút gốc mới sẽ được tạo ra và chiều cao của cây tăng lên 1 dẫn đến số lần truy xuất đĩa tăng lên 1. Theo cơ chế tràn đã trình bày ở trên, biến thể mới sẽ thực thi thao tác chèn 20 theo một cách hoàn toàn khác với cây B-tree nguyên thủy. Cây biến thể sau khi chèn 20 được thể hiện trong hình (c). Trong trường hợp này, nút D đã được điền đầy bởi các giá trị khóa liên tiếp (12, 13, 14, 15) do đó nút D sẽ được ghi vào bộ nhớ flash mà không bị tách. Sau đó, bản ghi với khóa 20 được chèn vào một nút rỗng mới E. Quá trình xây dựng cây theo cơ chế tràn giúp làm giảm đáng kể số lượng các thao tác trên bộ nhớ flash. Mặt khác, hiệu suất sử dụng không gian của các trang nhớ được tăng lên bởi vì các nút lá trong cây OMB luôn luôn đầy (không tách nút) trong khi các nút trong cây nguyên thủy luôn luôn chỉ đầy một nữa sau khi tách nút. Tương tự với thao tác chèn, thao tác xóa cũng được áp dụng cơ chế tràn cho phép một nút có số lượng giá trị khóa dưới mức cho phép của cây B-tree (<1/2 nút). Với một cây B-tree nguyên thủy, khi một nút có số lượng giá trị khóa dưới ngưỡng cho phép thì nút đó sẽ được gộp với các nút anh em lân cận của nó để tạo thành các nút mới có số lượng khóa thỏa mãn yêu cầu của cây B-tree. Hình 3 trình bày ví dụ về cơ chế tràn khi xóa các giá trị khóa của nút. Với thực tế là khoảng 80% các thao tác ghi trên các hệ thống là tuần tự [17-18], việc áp dụng cơ chế tràn này vào thực tế sẽ giúp cho việc triển khai cây chỉ mục B-tree trên bộ nhớ flash đạt hiệu suất cao. 172 KỶ YẾU HỘI THẢO KHOA HỌC QUỐC GIA CITA 2017 “CNTT VÀ ỨNG DỤNG TRONG CÁC LĨNH VỰC” Hình 3. Ví dụ xóa khóa trên cây B-tree 4 Đánh giá thực nghiệm Phần này trình bày kết quả thực nghiệm của biên thể mới và so sánh với hiệu suất của cây B-tree nguyên thủy, IBSF đại diện cho nhóm sử dụng bộ đệm, dIPL đại diện cho chóm thay đổi cấu trúc và RBFTL đại diện cho nhóm lai. Tất cả các cây B-tree được triển khai trên bộ nhớ flash giả lập với các thông số hoàn toàn giống với một bộ nhớ flash thật. Bộ nhớ này có thể đếm được các tác của nó. Bộ nhớ giả lập được cấu hình như sau: dung lượng 8GB; kích thước mỗi khối là 128kB, mỗi trang là 1KB. Mỗi nút của cây B-tree chứa 128 phần tử. Mỗi phần tử gồm có 4 byte giá trị khóa, 4 byte con trỏ trỏ đến nút con của nó. Giá trị khóa chỉ mục là các số tự nhiên duy nhất trong khoảng từ 1-100.000. Hiệu suất của các cây được đánh giá dựa trên số lượng thao tác và hiệu suất sử dụng không gian nhớ trong các khối nhớ. Để điều khiển việc phân bố giá trị khóa, chúng tôi sử dụng một giá trị rs gọi là tỷ lệ tuần tự (ratio of key sequence). Nếu rs = 1, các giá trị khóa được sắp xếp theo thứ tự tăng dần. Ngược lại, nếu rs = 0, các giá trị khóa hoàn toàn ngẫu nhiên và nếu rs = 0,5, 50% các giá trị khóa được sắp xếp tăng dần. Trong các thử nghiệm, chúng tôi sử dụng bộ đếm thao tác và bộ đếm thời gian hệ thống của bộ nhớ flash để đánh giá kết quả thực hiện. 4.1 Hiệu suất xây dựng cây B-tree Trong phần này, hiệu suất xây dựng các cây B-tree được trình bày và so sánh nhằm đánh giá hiệu quả của biến thể OMB. Hình 4 trình bày số lượng thao tác ghi khi chèn 100.000 bản ghi vào các cây với rs thay đổi. Nhìn chung biến thể OMB đạt hiệu suất tốt hơn các biến thể IBSF, dIPL và cây B-tree nguyên thủy. Đối với biến thể OMB, bởi vì nó không tách các nút lá trong các trường hợp giá trị rs cao (tính tuần tự cao) nên số lượng thao tác ghi giảm đáng kể. Do đó, hiệu suất của OMB tốt hơn rất nhiều so với các cây còn lại. Hiệu suất của IBSF với cơ chế tràn (IBSF+OMB) tăng khoảng 10,6% so với IBSF nguyên thủy. Tương tự như vậy, hiệu suất của dIPL+OMB, RBFTL+OMB và B-tree+OMB tốt hơn các cây dIPL, RBFTL, B-tree nguyên thủy lần lượt là 7,5%, 12,2%, và 15,7%. Trong trường hợp rs = 0 (các giá trị khóa ngẫu nhiên), hiệu suất của các biến thể OMB và biến thể nguyên thủy tương ứng gần như tương đương với nhau. Trong trường hợp này, cơ chế tràn không phát huy được hiệu quả của nó vì các nút luôn được chèn vào các giá trị khóa ngẫu nhiên dẫn đến thao tác tách nút diễn ra thường xuyên. Do đó số lượng thao tác ghi tăng lên đáng kể. Hồ Văn Phi, Nguyễn Văn Lợi 173 Hình 4. Hiệu suất ghi 4.2 Hiệu suất sử dụng không gian khối nhớ Hình 5 trình bày số lượng khối nhớ được sử dụng để lưu trữ dữ liệu của các cây B-tree. Từ hình ảnh cho thấy rõ ràng rằng số lượng khối nhớ mà các biến thể có OMB sử dụng để lưu dữ liệu ít hơn các biến thể nguyên thủy của chúng trong tất cả các trường hợp. Trong trường hợp rs = 1, các biến thể có OMB cần ít khối nhớ hơn cây nguyên thủy của nó trừ cây B-tree nguyên thủy bởi vì chúng không tách nút dẫn đến các nút lưu trong flash luôn luôn đầy trong trường hợp các khóa tuần tự. Ngược lại, nút trong các biến thể không có OMB luôn luôn đầy một nữa sau khi tách nút. Do đó chúng cần nhiều khối nhớ hơn. Số lượng khối nhớ mà các biên thể IBSF+OMB, dIPL+OMB, RBFTL+OMB và B-tree+OMB ít hơn các biến thể tương ứng của chúng lần lượt khoảng 18,4%, 15,5%, 19,8 và 21,6%. Hình 5. Hiệu suất sử dụng không gian nhớ 174 KỶ YẾU HỘI THẢO KHOA HỌC QUỐC GIA CITA 2017 “CNTT VÀ ỨNG DỤNG TRONG CÁC LĨNH VỰC” 5 Kết luận Bộ nhớ flash và cấu trúc dữ liệu cây B-tree được sử dụng phổ biến hiện nay nhớ vào ưu điểm của chúng. Tuy nhiên vì những hạn chế về mặt cấu tạo vật lý mà việc triển khai cây chỉ mục B-tree trên bộ nhớ flash gặp phải những vấn đề về hiệu suất thực hiện. Bài báo này trình bày cơ chế tràn mới cho cây chỉ mục B-tree trên bộ nhớ flash. Với cơ chế này, hiệu suất của cây chỉ mục và bộ nhớ flash tăng lên đáng kể nhờ vào việc giảm số lượng thao tác trên bộ nhớ flash. Qua các kết quả thực nghiệm cho thấy, cơ chế tràn OMB giúp cây chỉ mục trên bộ nhớ flash đạt hiệu quả cao và giúp bộ nhớ flash kéo dài tuổi thọ vì OMB giảm số lượng lớn thao tác xóa trên bộ nhớ flash. Tài liệu tham khảo 1. Shinde Pratibha et al.: Efficient Flash Translation layer for Flash Memory. International Journal of Scientific and Research Publications, Volume 3, Issue 4 (2013). 2. E.gal, S. Toledo.: Algorithms and data structures for flash memory. ACM Computing surveys 37, 2005, 138-163 (2015). 3. D. S. Batory.: B+-Trees and Indexed Sequential Files: A Performance Comparison. Proceeding of Special Interest Group on Management of Data, 30-39 (1981). 4. Chin-Hsien Wu et al.: An Efficient B-Tree Layer Implementation for Flash Memory Storage Systems. ACM Transactions on Embedded Computing Systems, Vol. 6, No. 3 (2007). 5. Hyun-Seob Lee and Dong-Ho Lee.: An Efficient Index Buffer Management Scheme for Implementing a B-Tree on NAND Flash Memory. Data & Knowledge Engineering, vol. 69, no.9, 901-916 (2010). 6. Xiaona Gong et al.: A Write-Optimized B-Tree Layer for NAND Flash. Proceeding of the 7th International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM), 1-4 (2011). 7. Devesh Agrawal et al.: Lazy-Adaptive Tree: An Optimized Index Structure for Flash Devices. Very Large Data Base 09 (2009). 8. Artem B. Bityuckiy.: JFFS3 design issues. Memory Technology Device Subsystem for Linux (2005). 9. Dongwon Kang, Dawoon Jung, Jeong-Uk Kang and Jin-Soo Kim.: µ -Tree: An Ordered Index Structure for NA-ND Flash Memory. EMSOFT’07 (2007). 10. Jung-Sang Ahn, Dongwon Kang, Dawoon Jung, Jin-Soo Kim, Member, IEEE, and Seungryoul Maeng.: µ*-Tree: An Ordered Index Structure for NAND Flash Memory with Adaptive Page Layout Scheme. IEEE Transactions on Computers, vol. 62, no. 4, 784-797 (2013). 11. Sang-Won Lee and Bongki Moon.: Design of Flash-Based DBMS: An In-Page Logging Approach. SIGMO-D’07, China (2007). 12. Gap-Joo Na, Sang-Won Lee, and Bongki Moon.: Dynamic In-Page Logging for B+-tree Index. IEEE Trans. Knowledge and Data Engineering, vol. 24, no.7, 1231-1243 (2012). 13. Yinan Li, Bingsheng He, Robin Jun Yang, Qiong Luo and Ke Yi.: Tree Indexing on Solid State Drives. Proceedings of International Conference on Very Large Data Bases (2009). 14. Hongchan Roh, Woo-Cheol Kim, Seungwoo Kim and Sanghyun Park.: A B-Tree Index Extension to Enhance Response Time and The Life Cycle of Flash Memory. Information Sciences, vol.179, no.18, 3136-3161 (2009). 15. Xiaoyan Xiang, Lihua Yue, Zhanzhan Liu, Peng Wei.: A Reliable B-Tree Implementation over Flash Memory. SAC’08, Brazil (2008). 16. Sungho Kim, Hongchan Roh, Daewook Lee and Sanghyun.: AS B-tree: A Study of an Efficient B+-tree for SSDs. Journal of Information Science & Engineering, Vol. 30 Issue 1, 85-90 (2014). 17. Drew Roselli et al.: A Comparison of File System Workloads. Proceedings of the 6th USENIX Conference on File and Storage Technologies, pp. 41-54 (2000). 18. Andrew W Leung et al.: “Measurement and Analysis of Large Scale Network File System Workloads. Proceedings of the 6th USENIX Conference on File and Storage Technologies, pp. 213-226 (2008).